第05章_图的广度优先遍历.md

第05章 图的广度优先遍历

5.1 从树的广度优先遍历，到图的广度优先遍历

广度优先遍历实际就是层序遍历

可以参考玩转算法与数据结构的视频教程和代码

• 5-6 层序遍历(广度优先遍历)
• 层序遍历参考代码

广度优先遍历实际就是用了一个队列，不断弹出父节点加入子节点的过程

深度优先遍历就是指前、中、后序遍历

可以参考玩转算法与数据结构的视频教程和代码

• 5-5 二分搜索树的遍历(深度优先遍历)
• 代码

5.2 广度优先遍历的实现

• 实现代码
• 测试代码

广度优先遍历的复杂度：O(V + E)

5.3 使用BFS求解单源路径

参考深度优先遍历的代码

• 实现代码
• 测试代码

5.4 广度优先遍历求单源路径的优化

BFS遍历到target就提前退出，这样可以极大地节省递归的成本,当前图的构造就只是为了求解当前两个点的路径

• 实现代码
• 测试代码

5.5 广度优先遍历求连通分量

和DFS基本相同

• 实现代码
• 测试代码

5.6 广度优先遍历实现环检测

和DFS的基本相同

• 实现代码
• 测试代码

5.7 广度优先遍历实现二分图检测

和DFS的基本相同

• 实现代码
• 测试代码

5.8 BFS的单源路径实际就是source到target得最短路径

实际就是求出了无权图中指定两点的最短路径，还有个小缺点就是只列出了最短路径经过点，而没有列出具体的最短路径的值

• 代码参考

代码的图示如下，左侧是DFS的单源路径问题，右侧是BFS的单源路径问题

5.9 无向图的最短路径，终极版

返回最短路径经过的点和最短路径的值，实际就是加了一个distance数组，记录了BFS过程中经过的点到起点source的距离(无权图默认边长是1，经过一条边加1即可)。测试的Graph就是上面的图

• 实现代码
• 测试代码

5.10 DFS和BFS的神奇联系

都转换成非递归的方式地话，DFS用地是Stack, BFS用的是Queue

为了方便看，stack和queue添加元素的方法都写成了add，删除元素的方法都写成了remove

进一步抽象，可以得到图的遍历都可以提取成如下的编程模型

下面图的x就是指存储遍历点的容器类型，当是Stack时就是深度优先遍历，当是Queue时就是广度优先遍历，其实也可以是其他的容器类型，比如是个随机弹出的容器类型，那么遍历就相当于是随机遍历了，这个思想在刘老师的《看地见的算法 7个经典应用诠释算法精髓》里有应用到