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)