图的遍历——BFS 与 DFS 深度优先和广度优先搜索｜图论算法

问题引入

有一天，你穿越到Clannad（炒鸡好看的游戏与番剧）的小镇。你知道小镇上的每个地方与每条路。小镇的某些地方可能会藏有实现愿望的光玉。现在你要出发去收集小镇上所有的光玉。

如图：

假设小镇中一个地方对应这张图的一个结点，你的出生点在古河面包店（0号位置），据题意，你需要一个地点都不落地走完整张图，这样才能收集完所有光玉。

BFS

广度优先搜索（Breadth First Search)：

属于一层一层地扩展，每次到一个点后，把这个点其他相邻点都记录下来，作为下一层的待访问结点。

根据这个概念，我们需要准备：

一个小本本

步骤：

1、每到达一个点（最开始是起点），观望一下周围哪些地点跟当前点相连，把这些点都添加在小本本上。

2、跳到小本本上记录的第一个地点（执行 1 步骤），然后把这个地点从小本本上擦除。

3、重复执行 2、直到小本本上没有记录任何点（此时已经到达了所有地点，后面有实例将证明）

根据上面的步骤，可以给出伪代码：

伪代码：把起点添加到小本本上；while (小本本上 有 地点) {跳到小本本上最上面的地点，假设为P点。 把P点从小本本上擦除。for ( 遍历所有 与P点相邻 的Q点 ) { if ( Q点不在小本本上 ) { 把 Q点 添加到小本本的最后面。 } }}

可以看出：小本本具有先进先出的性质，就是一个队列

把 0点 记在小本本上。

从小本本中取出 0点（到达 0点 ）， 观望一下，把1点、2点、7点记录在小本本上。这时小本本上 记录了1点、2点、7点。

（1点在前）从小本本中取出 1点，观望一下，把 4点、5点记录在小本本上。这时小本本上 记录了2点、7点、4点、5点。

从小本本中取出 2点，观望一下，把 4点 已经在小本本上了，不用记录。这时小本本上 记录了7点、4点、5点。

从小本本中取出 7点，观望一下，没有可以记录的点。这时小本本上 记录了4点、5点。

从小本本中取出 4点，观望一下，把 3点 记录在小本本上。这时小本本上 记录了5点、3点。

从小本本中取出 5点，观望一下，把 6点 记录在小本本上。这时小本本上 记录了3点、6点。

从小本本中取出 3点，观望一下，没有可以记录的点。这时小本本上 记录了6点。

从小本本中取出 6点，观望一下，没有可以记录的点。小本本已经没有记录任何点了，同时所有地点都走完啦。

DFS

深度优先搜索(Depth First Search)：

先选择一条路一直往前走，走到尽头后，就返回到上一个交叉路口选择另一条没走过的路。

一直重复，这样就能走完所有的地点。

（像不像老鼠走迷宫，一条路一条路地尝试）

根据这个寻路的过程，我们要知道：

每个结点能去到哪些其他结点。怎样返回到上一个交叉路口。关于返回到上一个路口，我们很容易想到递归。

递归的过程是 走到每一个相邻的结点

递归的边界是 走到尽头（即没有能走的结点 或者 每一个相邻结点都走完了)

下面是伪代码：

到达（ P点 ）{for( 从P点出发能去的相邻的点Q ){ if( 没有来过Q点 ){记录Q点到过了。 到达（ Q点 ） } } 返回P点前的一步}

解析：

递归函数： 到达（某点）

递归函数结束：当for循环（遍历所有能去的结点）结束

一条路已经走完了，返回到上一个交叉路口。

过程：

据说 下面的过程跟上面的图更配哦

1.从起点出发，进入递归函数——>到达0点

（到达0点）有1点 2点 7点相邻。从编号最小的开始。进入 ——到达1点

（到达0点 （到达1点）） 有 4点 5点相邻。 进入——到达4点（到达0点 （到达1点 （到达4点））有2点 3点 相邻。进入——到达2点

（到达0点 （到达1点 （到达4点 （到达2点）））这时0点访问过，这条路到尽头了，返回上一个路口——到达4点此时走完了 0——1——4——2 这条路

（到达0点 （到达1点 （到达4点））有2点 3点 相邻。2点访问过，进入——到达3点

（到达0点 （到达1点 （到达4点 （到达3点））这条路到尽头了，返回上一个路口——到达4点此时走完了 0——1——4——3 这条路

（到达0点 （到达1点 （到达4点））这条路到尽头了，返回上一个路口——到达1点此时走完了 0——1——4 这条路

（到达0点 （到达1点）） 有 4点 5点相邻。4点访问过了。 进入——到达5点

（到达0点 （到达1点 （到达5点））有6点相邻。进入——到达6点

（到达0点 （到达1点 （到达5点 （到达6点））这条路到尽头了，返回上一个路口——到达5点此时走完了0——1——5——6

（到达0点 （到达1点 （到达5点））这条路到尽头了，返回上一个路口——到达1点走完了0——1——5

（到达0点 （到达1点））这条路到尽头了，返回上一个路口——到达0点走完了0——1

（到达0点）有1点 2点 7点相邻。1点2点都访问过了，进入——到达7点

（到达0点 （到达7点））这条路到尽头了，返回上一个路口——到达0点走完了0——7