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)