AI模型学习——上下文管理
2026/1/16 13:34:37
题目背景
给定一个包含 n 个点和 m 条边的无向图。点从 1 到 n 编号。
请分别使用深度优先搜索 (DFS) 和 广度优先搜索 (BFS) 遍历该图，并输出遍历序列。
题目要求
存储结构：使用邻接表（链式前向星）存储图结构。
遍历起点：两次遍历均从1号节点开始。
邻居顺序：在遍历每个节点的邻居时，遵循链式前向星“头插法”的特性（即：输入顺序靠后的边，在遍历时会优先访问）。
输出要求：
第一行输出 DFS 遍历序列。
第二行输出 BFS 遍历序列。
每个数字后面跟一个空格。
输入格式
第一行包含两个正整数 n 和 m，表示点数和边数。
接下来 m 行，每行包含两个整数 u, v，表示点 u 和点 v 之间有一条无向边。
输出格式
第一行：DFS 遍历序列。
第二行：BFS 遍历序列。
数据范围
1<=n<=1000
1<=m<=2000
样例输入
8 9 1 2 1 3 2 4 2 5 4 8 5 8 3 6 3 7 6 7样例输出
(注意：链式前向星由于是头插法，邻接点的顺序通常是输入顺序的倒序，所以遍历结果可能与直觉（从小到大）不同，但符合代码逻辑)
1 3 7 6 2 5 8 4 1 3 2 7 6 5 4 8#include <iostream> #include <cstring> #include <queue> using namespace std; int h[2000]; int vtex[4000]; int nxt[4000]; int vis[2000]; int idx=0; queue<int> q; void dfs(int x){ cout<<x<<" ";//输出这个节点 int p=h[x];//h[x]存的是x下一个相邻节点在vtex数组中的编号 vtex[p]的值就是相邻节点 while(p!=-1){//如果指针指向的节点不为空 if(vis[vtex[p]]==0){//如果相邻节点没走过，就可以去走 vis[vtex[p]]=1;//先标记为走过 dfs(vtex[p]);//然后从相邻节点继续往下走 } p=nxt[p];//让指针变成指向链表的下一个指针 } } void bfs(int x){ q.push(x); while(!q.empty()){ int tmp=q.front();//访问队首元素 cout<<tmp<<" "; q.pop();//删除队首 int p=h[tmp]; while(p!=-1){//如果指向下一个数的指针不为空 if(vis[vtex[p]]==0){//如果下一个数没被访问过 q.push(vtex[p]);//入队 vis[vtex[p]]=1;//标记为访问过 p=nxt[p];//更新指针指向下一个数 } else p=nxt[p];//如果被访问过更新指针指向下一个数 直到指向下一个数的指针为空 } } } void addedge(int a,int b){ vtex[idx]=b; nxt[idx]=h[a]; h[a]=idx++; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m;//点数 边数 cin>>n>>m; //先把图的邻接表建出来 memset(h,-1,sizeof(h));//初始化h数组 for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; addedge(u,v); addedge(v,u); } //图的深搜遍历 vis[1]=1; dfs(1); cout<<endl; memset(vis,0,sizeof(vis));//进行完深搜再去进行广搜要对vis数组初始化 /*输出邻接表 for(int i=1;i<=n;i++){ cout<<i<<": "; int tmp=h[i]; while(tmp!=-1){ cout<<vtex[tmp]<<" "; tmp=nxt[tmp]; } cout<<endl; } */ //图的广搜遍历 vis[1]=1; bfs(1); return 0; }1. 为什么选择链式前向星？
在竞赛和工程中，我们常用三种方式存图：
邻接矩阵：O(N^2)空间，太浪费，稀疏图（点多边少）直接爆炸。
Vector 邻接表：动态扩容方便，但有额外内存开销，且 vector 的常数较大。
链式前向星：本质是静态数组模拟单链表。它内存连续、没有碎片、空间可控（O(M)），是处理大规模图论题的最优解。
2. 核心原理：内存里的“穿针引线”
链式前向星由三个核心数组构成，它们配合完成“由点找边”的任务：
h[u](Head)：索引数组。存储节点 u 的最后一条被加入的边的编号（即链表头）。初始化：必须为
-1，代表空链表。
vtex[i](Vertex)：数据数组。记录第 i 条边指向的终点节点。nxt[i](Next)：指针数组。记录第 i 条边的下一条边的编号（同起点的上一条加入的边）。
2.1 插入过程模拟（头插法）
假设我们要给节点 1 添加两条边：先加 1->2，后加 1->5。
idx 是边的计数器，从 0 开始。
初始状态：
h[1] = -1加入边 1->2 (idx=0)：
记录终点：
vtex[0] = 2链接旧头：
nxt[0] = h[1](即 -1)更新新头：
h[1] = 0
加入边 1->5 (idx=1)：
记录终点：
vtex[1] = 5链接旧头：
nxt[1] = h[1](即 0)更新新头：
h[1] = 1
结果：当我们遍历节点 1 时，从 h[1] 开始：
先访问 idx=1 (终点5)->顺着 nxt[1] 找 idx=0 (终点2)->顺着 nxt[0] 找 -1 (结束)。
结论：这就是为什么链式前向星遍历顺序与输入顺序相反（LIFO 后进先出）。
3. 无向图的“空间陷阱”
无向图的一条边 u-v 在逻辑上等价于两条有向边 u->v 和 v->u。
这意味着，如果题目给出 m 条边，我们实际调用的 addedge 次数是 2m。
易错点：
vtex和nxt数组的大小必须开到2*M。后果：如果不乘以 2，存最后几条反向边时数组越界，直接 Runtime Error。
4. 搜索算法的关键细节
DFS (递归实现的深度优先)
机制：利用系统栈进行回溯。
要点：
vis数组用于剪枝。只要nxt指针没指到-1，就通过vtex取出邻居，判断是否访问过，没访问过则递归。
BFS (队列实现的广度优先)
机制：利用
queue维护访问层级。法则：标记必须在入队 (Push) 时进行！
正确：Push -> Mark。保证队列里不会有重复节点。
错误：Pop -> Mark。会导致同一层级的节点将同一个邻居重复加入队列，在稠密图中时间复杂度从 O(N+M) 退化为指数级。
5. 复杂度分析
设点数为 N，边数为 M（无向图边数为 2M）。
空间复杂度：O(N + 2M)。由三个数组决定，线性空间，非常优秀。
时间复杂度：
建图：O(M)。
DFS/BFS：O(N + 2M)。每个点访问一次，每条边访问一次。
总结：
这道题不仅是图论入门，更是对指针操作和内存管理的一次降维打击训练。掌握了链式前向星，就掌握了图论高性能实现的基石。