[数据结构与算法]图的遍历---深度优先搜索+广度优先搜索

一、深度优先搜索

1.基本思想

1.1首先访问图中某一个顶点A，并且以该顶点为出发点

1.2任选一个与顶点A邻接的未被访问的顶点B，访问B

1.3以B为新的出发点（新的A）继续进行深度优先搜索，直至图的所有顶点都被访问到

2.算法分析

2.1对于非连通图也可遍历到，需要在深度优先搜索的执行函数用循环访问未被访问顶点

2.2（对于有n个顶点，e条边的图）邻接矩阵遍历时间O(n^2)，邻接表遍历时间O(n+e)

3.算法应用

3.1求深度优先生成树

3.2判断图是否连通

3.3求图的连通分量

二、广度优先搜索

1.算法思想

1.0类似树的按层次遍历

1.1首先找到图中的一个顶点A

1.2然后依次访问顶点A的所有邻接点B\C\D\\\（入队列）

1.3再依次以BCD为顶点，访问未访问邻接点，直至所有顶点都被访问到（循环条件---队列非空）

2.算法分析

2.1可以应对非连通图（for循环内嵌套while循环，for循环保证所有顶点都被遍历，while循环保证邻接顶点都被遍历到）

2.2（对于n个顶点，e条边的图）邻接矩阵时间代价O(n^2)，邻接表时间代价O(n+e)

3.算法应用

3.1求广度优先生成树

3.2判断图是否连续

3.3求图的连通分量

希望大家一起学习，共同进步，如果有疑问或错误欢迎联系笔者。