首页 > 代码库 > 图论(三)------广度优先搜索与单源无权最短路径
图论(三)------广度优先搜索与单源无权最短路径
有一个无权的图G，使用某个顶点s作为输入参数，找出从s到其它顶点的最短路径。这样，只要计算包含在路径中的边数就可以了。
比如，一个word ladder problem，一次只变换一个字母，找出从fool到sage的最短路径。
可用的单词可以转化为一个图：
首先寻找与fool距离为1的顶点：
然后可以寻找距离fool为2的顶点：
最后，搜索出全部顶点：
这样搜索一个图的方法称为广度优先搜索：距开始点最近的那些顶点首先被搜索，最远的那些顶点最后被搜索。
def unweighted(G,v): queue=[] path_length={} path_length[v]=0 queue.append(v) while queue: v=queue.pop(0) for i in v.getNeighbors(): if i not in path_length: path_length[i]=path_length[v]+1 queue.append(i) return path_length
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。