python广度优先搜索得到两点间最短路径 - CSDN文库

55 浏览量更新于2023-05-11 收藏 72KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

python广度优先搜索得到两点间最短路径广度优先搜索得到两点间最短路径

主要为大家详细介绍了python广度优先搜索得到两点间最短路径，具有一定的参考价值，感兴趣的小伙伴们可

以参考一下

前言前言

之前一直写不出来，这周周日花了一下午终于弄懂了，顺便放博客里，方便以后忘记了再看看。

要实现的是输入一张图，起点，终点，输出起点和终点之间的最短路径。

广度优先搜索广度优先搜索

适用范围：适用范围：无权重的图，与深度优先搜索相比，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较

快

复杂度：复杂度：时间复杂度为O(V+E),V为顶点数，E为边数

思路思路

广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索；

比如下图：

从0结点开始搜索的话，一开始是0、将0加入队列中；

然后下一层，0可以到达的有1,2,4,将他们加入队列中；

接下来是1，1能到达的且未被访问的是结点3

顺序就是 0， 1，2，4， 3，这里用下划线表示每一层搜索得到的结点；

每一次用cur = que[head]取出头指针指向的结点，并搜索它能到达的结点；因此，可以用一个队列que来保存已经访问过的

结点,队列有头指针head以及尾指针tail,起点start与结点i有边并且结点i未被访问过，则将该结点加入队列中,tail指针往后移

动；当tail等于顶点数时算法结束

对于每一次while循环，head都加一，也就是往右边移动，比如一开始head位置是0，下一层的时候head位置元素就为1，也

就是搜索与结点1有边的且未被访问的结点

用一个数组book来标识结点i是否已经被访问过；用字典来保存起点到各个点的最短路径；

代码如下：

import numpy as np

ini_matrix = [

[0, 1, 1, 0, 1],

[1, 0, 0, 1, 0],

[1, 0, 0, 0, 1],

[0, 1, 0, 0, 0],

[1, 0, 1, 0, 0]

]

def bfs(matrix_para, start_point_para, end_point_para):

"""

广度优先搜索

:param matrix_para 图

:param start_point_para 起点

:param end_point_para 终点

:return: 返回关联度

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

weixin_38712874

粉丝: 10
资源: 947

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈