图的遍历思维脑图思维导图
广度优先遍历，深度优先遍历全内容分解
树图思维导图提供 图的遍历思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 图的遍历思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0b02915a094a66a429f3bf1bd884b162
思维导图大纲
图的遍历思维导图模板大纲
广度优先遍历（BFS）
要点
需要一个辅助队列
标记哪些顶点被访问过
找到与一个顶点相邻的所有顶点
类似树的层序遍历
复杂度
空间复杂度
O（|V|）——辅助队列
最坏情况：一个顶点和其他顶点都有边，O（|V|）
最好情况：各顶点串成一条线，O（1）
时间复杂度
邻接表：O(|V|+|E|)
邻接矩阵：O(|V^2|)
广度优先生成树
由广度优先遍历确定的树
邻接表存储的图表示方式不唯一，遍历序列、生成树也不唯一
遍历非连通图得到广度优先生成森林
代码必须会背
深度优先遍历（DFS）
要点
类似树的先根遍历
递归地深入探索未被访问的邻接点
复杂度
空间复杂度
O（|V|）——递归调用栈
最好情况：一个顶点和其他顶点都有边，O（1）
最坏情况：各顶点串成一条线，O（|V|）
时间复杂度
邻接矩阵：O(|V^2|)
邻接表：O(|V|+|E|)
深度优先生成树
由深度优先遍历确定的树
邻接表存储的图表示方式不唯一，遍历序列、生成树也不唯一
遍历非连通图得到深度优先生成森林
代码必须会背
值得注意
图的遍历与连通性
无向图
DFS/BFS调用次数 = 连通分量数
有向图
若从起始顶点到其他顶点都有路径，则只调用1次DFS/BFS函数
对于强连通图，从任意顶点出发都只调用1次DFS/BFS函数
DFS可以用来判断图中是否存在回路
对无向图，dfs多加一个参数parent，代表父节点，若访问到某个顶点时，其某个邻接点不是父节点，却访问过，说明有回路！
对有向图，一个节点在初始状态为白色，DFS访问该节点时染成灰色，并在DFS退出时染成黑色。如果DFS的循环中发现了灰色节点，则说明有环。
一般来说，广度优先生成树的树高≤深度优先生成树
沪公网安备 31011502019485号
上海工商