图的遍历DFS和BFS

复习定位

图的遍历是从图的一个顶点出发——沿着边访问所有顶点——每个顶点仅被访问一次。DFS使用栈(或递归)实现——深入一条路径到底再回溯。BFS使用队列实现——先访问离起始点最近的顶点——再逐层向外扩展。BFS可以用于无权图单源最短路径——DFS常与拓扑排序和环路检测相结合。

深度优先搜索DFS

DFS的策略——尽可能深入一个分支再回溯：

1. 访问起始顶点v——标记为已访问
2. 从v的邻接顶点中选一个未访问的w——递归调用DFS(w)
3. 如果v的所有邻接项都已访问——回溯到v的上一个顶点

DFS可以用递归实现(简单)或用显式栈实现(避免递归深度过大导致栈溢出)。

DFS的遍历序列不唯一——取决于邻接顶点的处理顺序。

应用场景：

• 判断图中有无环——检测DFS过程中是否遇到已访问的顶点(后向边)
• 查找图的连通分量——DFS的次数等于连通分量数
• 拓扑排序——按DFS完成时间的逆序输出顶点
• 对无环有向图的强连通分量(Kosaraju/Tarjan算法的基础)

广度优先搜索BFS

BFS从起始顶点开始——先访问所有距离为1的邻接点——然后所有距离为2的点——逐层向外：

1. 将起始顶点v入队列、标记为已访问
2. 队非空时：
   a. 出队列得到顶点u
   b. 访问顶点u的所有未访问的邻接点——将它们入队并标记为已访问

BFS使用队列保证先入先处理——从而达到"逐层遍历"的效果。

BFS的一个重要性质：在无权图上——BFS第一次访问某顶点时的路径就是从起始点到该顶点的最短路径(最少边数)。因为BFS按层处理——位于第i层的顶点距离输入顶点i条边。

应用场景：

• 无权图的最短路径
• 判断图是否为二分图——从某顶点出发BFS——给每层交替着色——如果出现相邻顶点同色则非二分图

复杂度分析

时间复杂度：邻接表——DFS和BFS都需要访问每个顶点一次、每条边至少一次——O(V+E)。邻接矩阵——遍历每个顶点的邻接点需一整行扫描O(V)——总复杂度O(V²)。

空间复杂度：BFS的队列在最差情况下(连通图)需要存大部分顶点——O(V)。DFS递归调用栈深度在最坏情况下等于顶点数(一条单链)——O(V)。

复习检查

1. 在邻接表存储的图中DFS遍历所有顶点的复杂度为什么是O(V+E)——其中访问每个邻接顶点向量的时间和累计边数的访问项的关系是什么？

2. BFS怎么用来求无权图的最短路径——第一次到达目标顶点时经过的边数为什么就是最短路径长度——为什么下一步找到的可能不是最短路径(因为可能有其他路径但被此层次覆盖的顶点已经在队列了)？

3. 如果图是一个环(所有顶点组成一个环)——DFS和BFS分别会以什么顺序访问顶点(假设从节点1依次搜索)——画出两种访问顺序。

4. 有向图中使用DFS检测有向环——当在遍历一个新顶点v的过程中——如果v的某个邻接点已经被访问(在当前的递归栈中)——说明检测到了有向边形成的环(后向边)。解释这个检测过程和isDAG的判定。

5. DFS遍历非连通图需要几次调用DFS(BFS同理)？这个次数对应图的什么性质——连通分量数？