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

文章目录

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

" 深度优先搜索 " 英文名称是 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 为初始结点继续进行遍历 , 进行回溯 , 所有的结点都已经遍历 , 递归结束 ;

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

文章目录

相关推荐