广度优先搜索和深度优先搜索的基本思想（广度优先搜索与深度优先搜索各有什么特点？）



文章目录

图 的 遍历 就是 对 图 中的 结点 进行遍历 , 遍历 结点 有如下两种策略 :

" 深度优先搜索 " 英文名称是 Depth First Search , 简称 DFS ;

DFS 基本思想 :

深度优先搜索算法步骤 :

以下图为例 , 说明 DFS 搜索步骤 ; 初始结点 A ;

初始结点 为 A , 开始进行 DFS :

访问 初始结点 A , 并将该 初始结点 A 标记为 " 已访问 " ;

查找 初始结点 A 的 第一个 邻接节点 B ;

查询邻接节点 B 是否存在 ; 邻接节点 B 结点存在 ;

查询邻接节点 B 是否被访问 ; 邻接节点 B 结点存在 并且 没有被访问 , 那么 对 邻接节点 B 结点 进行 深度优先遍历 , 将 邻接节点 B 结点 作为 新的 初始结点 , 从 ① 步骤开始执行 ;

访问 初始结点 B , 并将该 初始结点 B 标记为 " 已访问 " ;

查找 初始结点 B 的 第一个 邻接节点 A ;

查询邻接节点 A 是否存在 ; 邻接节点 A 结点存在 ;

查询邻接节点 A 是否被访问 ; 邻接节点 A 结点 存在 但是 被访问了 , 那么 查找 B 结点的 下一个 邻接节点 , 转到步骤 ③ 执行 ;

查找 结点 B 的 第二个 邻接节点 C ;

查询邻接节点 C 是否存在 ; 邻接节点 C 结点存在 ;

查询邻接节点 C 是否被访问 ; 邻接节点 C 结点存在 并且 没有被访问 , 那么 对 邻接节点 C 结点 进行 深度优先遍历 , 将 邻接节点 C 结点 作为 新的 初始结点 , 从 ① 步骤开始执行 ;

访问 初始结点 C , 并将该 初始结点 C 标记为 " 已访问 " ;

查找 初始结点 C 的 第一个 邻接节点 A ;

查询邻接节点 A 是否存在 ; 邻接节点 A 结点存在 ;

查询邻接节点 A 是否被访问 ; 邻接节点 A 结点 存在 但是 被访问了 , 那么 查找 C 结点的 下一个 邻接节点 , 转到步骤 ③ 执行 ;

查找 结点 C 的 第二个 邻接节点 B ;

查询邻接节点 B 是否存在 ; 邻接节点 B 结点存在 ;

查询邻接节点 B 是否被访问 ; 邻接节点 B 结点 存在 但是 被访问了 , 那么 查找 C 结点的 下一个 邻接节点 , 转到步骤 ③ 执行 ;

查找 结点 C 的 第三个 邻接节点 ;

C 的第三个 邻接结点 不存在 , 回到 ① 查找 初始结点 B 的下一个 邻接节点 ;

在 第二轮递归 中 , 已经查找了 B 的 2 个邻接结点了 , 开始查找 B 的 第 3 个邻接结点 ;

查找 结点 B 的 第三个 邻接节点 D ;

查询邻接节点 D 是否存在 ; 邻接节点 D 结点存在 ;

查询邻接节点 D 是否被访问 ; 邻接节点 D 结点存在 并且 没有被访问 , 那么 对 邻接节点 D 结点 进行 深度优先遍历 , 将 邻接节点 D 结点 作为 新的 初始结点 , 从 ① 步骤开始执行 ;

访问 初始结点 D , 并将该 初始结点 D 标记为 " 已访问 " ;

查找 初始结点 D 的 第一个 邻接节点 B ;

查询邻接节点 B 是否存在 ; 邻接节点 B 结点存在 ;

查询邻接节点 B 是否被访问 ; 邻接节点 B 结点 存在 但是 被访问了 , 那么 查找 D 结点的 下一个 邻接节点 , 转到步骤 ③ 执行 ;

查找 结点 D 的 第二个 邻接节点 ;

D 的第三个 邻接结点 不存在 , 回到 ① 查找 初始结点 B 的下一个 邻接节点 ;

在 第四轮递归 中 , 已经查找了 B 的 3 个邻接结点了 , 开始查找 B 的 第 4 个邻接结点 ;

查找 结点 B 的 第四个 邻接节点 E ;

查询邻接节点 E 是否存在 ; 邻接节点 E 结点存在 ;

查询邻接节点 E 是否被访问 ; 邻接节点 E 结点存在 并且 没有被访问 , 那么 对 邻接节点 E 结点 进行 深度优先遍历 , 将 邻接节点 E 结点 作为 新的 初始结点 , 从 ① 步骤开始执行 ;

访问 初始结点 E , 并将该 初始结点 E 标记为 " 已访问 " ;

查找 初始结点 E 的 第一个 邻接节点 B ;

查询邻接节点 B 是否存在 ; 邻接节点 B 结点存在 ;

查询邻接节点 B 是否被访问 ; 邻接节点 B 结点 存在 但是 被访问了 , 那么 查找 D 结点的 下一个 邻接节点 , 转到步骤 ③ 执行 ;

查找 结点 B 的 第五个 邻接节点 ;

B 的第五个 邻接结点 不存在 , 回到 ① 查找 初始结点 A 的下一个 邻接节点 ;

继续回溯到 A 结点 , 查找 A 结点的 第二个 邻接结点 C , 然后 以 C 为初始结点继续进行遍历 , 进行回溯 , 所有的结点都已经遍历 , 递归结束 ;

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rgzn-sdxx/33767.html