(算法理论)图遍历(北京地铁导航应用)(python)
发布时间
阅读量：
阅读量
介绍两种图的遍历算法，即广度优先搜索（BFS）与深度优先搜索（DFS）。
在物理存储层面，图结构通常采用邻接表的方式进行表示，而邻接表在Python语言中则是通过字典数据结构来实现的。
以下为这两种遍历方法的具体代码实现：
def bfsTravel(graph, source):
# 传入的参数为邻接表存储的图和一个开始遍历的源节点
frontiers = [source] # 表示前驱节点
travel = [source] # 表示遍历过的节点
# 当前驱节点为空时停止遍历
while frontiers:
nexts = [] # 当前层的节点（相比frontier是下一层）
for frontier in frontiers:
for current in graph[frontier]: # 遍历当前层的节点
if current not in travel: # 判断是否访问过
travel.append(current) # 没有访问过则入队
nexts.append(curren全部评论 (0)
还没有任何评论哟~