python有向无权图遍历指定两点路径并排序输出

有向无权图简介

图是作为数据结构的一种类型，有向无权图是指有方向但没有方向路径权值。

python如何模拟有向无权图

利用列表模拟，看作为邻接表。邻接表是图的一种表示方法。 关于数据结构更多可以查看这篇博文： 执念斩长河专栏数据结构–目录

实例：python搜索图中指定两点的最短路径

实例用图： 实验效果： 实验代码：

# -*- coding:utf-8 -*- def searchGraph(graph,start,end): results = [] generatePath(graph,[start],end,results) results.sort(key=lambda x:len(x)) return results def generatePath(graph,path,end,results): state = path[-1] if state == end: results.append(path) else: for arc in graph[state]: if arc not in path: generatePath(graph,path + [arc],end,results) if __name__ == '__main__': Graph = {'A':['B','C','D'], 'B':['E'], 'C':['D','F'], 'D':['B','E','G'], 'E':[], 'F':['D','G'], 'G':['E']} r = searchGraph(Graph,'A','E') print('*************************') print(' path A to E') print('*************************') if not r: print('很遗憾，无此路径...') else: for i in r: print(i)