广度优先搜索递归（广度优先搜索求简单路径）

科技前沿 • 2025-04-30 17:17 • 阅读 45

大家好，我是讯享网，很高兴认识大家。

 <tbody> <tr> <td id="artContent" style="max-width: 656px;"> <div style="width: 656px; margin: 0; padding: 0; height: 0;"></div>

给定一幅图和一个起点 s，“从 s 到给定目的顶点 v 是否存在一条路径？如果有，找出这条路径。”这类问题叫单点路径问题

深度优先搜索用一个递归方法来遍历所有顶点。

在访问其中一个顶点时：
将它标记为已访问；
递归地访问它的所有没有被标记过的邻居顶点。

深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比

使用深度优先搜索得到从给定起点到任意标记顶点的路径所需的时间与路径的长度成正比。

给定一幅图和一个起点 s，“从 s到给定目的顶点 v是否存在一条路径？如果有，找出其中最短的那条（所含边数最少）。”这类问题叫单点最短路径问题。

要找到从 s 到 v 的最短路径，从 s 开始，在所有由一条边就可以到达的顶点中寻找 v，如果找不到我们就继续在与 s 距离两条边的所有顶点中查找 v，如此一直进行，直到找到v。

在搜索中我们都会先将起点存入数据结构中，然后重复以下步骤直到数据结构被清空：
取其中的下一个顶点并标记它；
将 v 的所有相邻而又未被标记的顶点加入数据结构。

对于从 s 可达的任意顶点 v，广度优先搜索都能找到一条从 s 到 v 的最短路径（没有其他从 s 到 v 的路径所含的边比这条路径更少）

广度优先搜索所需的时间在最坏情况下和 V+E 成正比

这两个算法的不同之处在于从数据结构中获取下一个顶点的规则（对于广度优先搜索来说是最早加入的顶点，对于深度优先搜索来说是最晚加入的顶点）

讯享网 </td> </tr> </tbody>

广度优先搜索 递归（广度优先搜索求简单路径）