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



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

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

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

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

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

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

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

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

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

版权声明：

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

转载请注明出处，原文链接：https://www.xkablog.com/jszy-jszl/51559.html