25考研数据结构复习·6.3图的遍历

广度优先遍历

🌲 参考树的遍历——不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点

🖼️ 图的遍历——搜索相邻的顶点时，有可能搜到已经访问过的顶点

广度优先遍历要点

1. 找到与一个顶点相邻的所有顶点
2. 标记哪些顶点被访问过（visited[]）
3. 需要一个辅助队列
4. 处理非连通图——遍历一轮后，检查visited[]的值是否还有false，如果有再一次调用BFS函数

遍历序列的可变性

1. 同一个图的邻接矩阵的表示方式唯一，因此广度优先遍历序列唯一
2. 同一个图的邻接表的表示方式不唯一，因此广度优先遍历序列不唯一

性能分析

最坏情况下，空间复杂度为O(|V|)——辅助队列

时间复杂度

邻接矩阵

访问|V|个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|V|)的时间，而总共由|V|个顶点，时间复杂度=O(|V|^2)

邻接表

访问|V|个顶点需要O(|V|)的时间

查找各个顶点的邻接点都需要O(|E|)的时间，时间复杂度=O(|V|+|E|)

广度优先生成树

定义：在广度遍历的过程中，可以得到一棵遍历树。

1. 同一个图的邻接矩阵存储表示唯一，因此其广度优先生成树也是唯一
2. 同一个图的邻接表存储表示不唯一，因此其广度优先生成树也不唯一

遍历非连通图得到广度优先生成森林

深度优先遍历

性能分析

最坏情况下，空间复杂度为O(|V|)——递归工作栈；最好情况;O(1)

时间复杂度=访问各结点所需时间+探索各条边所需时间

邻接矩阵

访问|V|个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|V|)的时间，而总共由|V|个顶点，时间复杂度=O(|V|^2)

邻接表

访问|V|个顶点需要O(|V|)的时间

查找各个顶点的邻接点都需要O(|E|)的时间，时间复杂度=O(|V|+|E|)

深度优先生成树

对连通图调用DFS才能产生深度有限生成树

遍历非连通图得到深度优先生成森林

图的遍历与图的连通性

1. 无向图进行DFS/BFS遍历
   1. 调用DFS/BFS函数的次数=连通分量数
   2. 对于连通图，只需调用1次BFS/DFS
2. 有向图进行DFS/BFS遍历
   1. 调用DFS/BFS函数的次数要具体问题具体分析
   2. 若起始顶点到其他各顶点都有路径，则只需要调用1次DFS/BFS函数
   3. 对于强连通图，从任一结点出发都只需调用1次DFS/BFS