大家好，欢迎来到IT知识分享网。
点击这里看上一部分图的基本概念与存图的两种方式邻接矩阵，邻接表
如果觉得有帮助的话，可以转发点赞支持一下哦！
图的遍历
问题引入
有一天，你穿越到Clannad(炒鸡好看的游戏与番剧)的小镇。你知道小镇上的每个地方与每条路。小镇的某些地方可能会藏有实现愿望的光玉。现在你要出发去收集小镇上所有的光玉。
如图：
假设小镇中一个地方对应这张图的一个结点，你的出生点在古河面包店(0号位置)，据题意，你需要一个地点都不落地走完整张图，这样才能收集完所有光玉。
BFS
广度优先搜索(Breadth First Search)：
属于一层一层地扩展，每次到一个点后，把这个点其他相邻点都记录下来，作为下一层的待访问结点。
根据这个概念，我们需要准备：
- 一个小本本
步骤：
- 每到达一个点(最开始是起点)，观望一下周围哪些地点跟当前点相连，把这些点都添加在小本本上。
- 跳到小本本上记录的第一个地点(执行 1 步骤)，然后把这个地点从小本本上擦除。
- 重复执行 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
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/157144.html
