首页 > 代码库 > 图的遍历算法
图的遍历算法
1、连通图的宽度优先搜索（BFS）
（1）算法思路
准备：起点v 和一个空队列Q 。
① 将v 打上已訪问标记。并将 v 放入队列Q 。
② 取出队列 Q 的 队首元素 u 。搜索全部与 u 相邻的顶点。假设 w 与u 相邻且未訪问， 则将w 打 上已訪问标记。并将 w 放入队列Q 。
③ 反复②。直到队列Q 空
准备：起点v 和一个空队列Q 。
① 将v 打上已訪问标记。并将 v 放入队列Q 。
② 取出队列 Q 的 队首元素 u 。搜索全部与 u 相邻的顶点。假设 w 与u 相邻且未訪问， 则将w 打 上已訪问标记。并将 w 放入队列Q 。
③ 反复②。直到队列Q 空
（2）算法代码：
（3）复杂性分析
（4）宽度优先生成树
2、一般图的宽度优先遍历
3、连通图的深度优先搜索（DFS）
（3）深度优先生成树
图的遍历算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。