Python 模式 - 實現圖
警告
此頁面保留在此處僅出於歷史原因，並且可能包含過時或不正確的資訊。
find_shortest_path 為“接近最優”。8/11/19：修復了意外使用 find_graph() 而不是 find_path() 的問題
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation. All rights reserved. Licensed under the PSF license.
圖是由邊或弧連線的節點組成的網路。在有向圖中，節點之間的連線具有方向，稱為弧；在無向圖中，連線沒有方向，稱為邊。我們主要討論有向圖。圖的演算法包括查詢兩個節點之間的路徑、查詢兩個節點之間的最短路徑、確定圖中的迴圈（迴圈是從一個節點到自身的非空路徑）、查詢到達所有節點的路徑（著名的“旅行推銷員問題”）等等。有時，圖的節點或弧具有與之相關的權重或成本，我們有興趣找到最便宜的路徑。
關於圖演算法有大量的文獻，它是離散數學的重要組成部分。圖在計算機演算法中也有許多實際用途。在網路管理中可以找到明顯的例子，但在許多其他領域也存在大量例子。例如，計算機程式中的呼叫者-被呼叫者關係可以看作一個圖（其中迴圈表示遞迴，而無法到達的節點表示死程式碼）。
很少有程式語言直接支援將圖作為資料型別，Python 也不例外。但是，圖很容易用列表和字典構建。例如，這是一個簡單的圖（我不能在這些列中使用圖形，所以我寫下圖的弧）：
A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C
該圖有六個節點 (A-F) 和八個弧。它可以由以下 Python 資料結構表示： graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}
這是一個字典，其鍵是圖的節點。對於每個鍵，對應的值是一個列表，其中包含透過從此節點直接引出的弧連線的節點。這已經是最簡單的了（甚至更簡單，節點可以用數字而不是名稱表示，但名稱更方便，並且可以很容易地攜帶更多資訊，例如城市名稱）。讓我們編寫一個簡單的函式來確定兩個節點之間的路徑。它將圖以及起始節點和結束節點作為引數。它將返回一個包含路徑的節點列表（包括起始節點和結束節點）。當找不到路徑時，它返回 None。返回的路徑上不會出現同一節點多次（即，它不會包含迴圈）。該演算法使用一種稱為回溯的重要技術：它依次嘗試每種可能性，直到找到解決方案。
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None
示例執行（使用上面的圖） >>> find_path(graph, 'A', 'D')
['A', 'B', 'C', 'D']
>>>
第二個 'if' 語句僅在存在被列為弧的終點但本身沒有引出弧的節點，並且根本沒有在圖中列出的情況下才是必要的。這樣的節點也可以包含在圖中，其中包含一個空的引出弧列表，但有時不要求這樣做會更方便。請注意，雖然使用者使用三個引數呼叫 find_path()，但它使用第四個引數呼叫自身：已遍歷的路徑。此引數的預設值是空列表 '[]'，表示尚未遍歷任何節點。此引數用於避免迴圈（'for' 迴圈內的第一個 'if'）。 'path' 引數不會被修改：賦值 "path = path + [start]" 會建立一個新列表。如果我們改為編寫 "path.append(start)"，則會修改呼叫者中的變數 'path'，導致災難性的結果。（使用元組，我們可以確信這種情況不會發生，但代價是必須編寫 "path = path + (start,)"，因為 "(start)" 不是單例元組 -- 它只是一個帶括號的表示式。）
很容易更改此函式以返回所有路徑（無迴圈）的列表，而不是它找到的第一條路徑：
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph.has_key(start):
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
示例執行 >>> find_all_paths(graph, 'A', 'D')
[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]
>>>
另一個變體找到最短路徑： def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
示例執行 >>> find_shortest_path(graph, 'A', 'D')
['A', 'C', 'D']
>>>
更新： Eryk Kopczyński 指出這些函式並非最優。相反，“此程式以指數時間執行，而使用 BFS [廣度優先搜尋] 可以線上性時間內完成 find_shortest_path。此外，線性 BFS 更簡單：”
# Code by Eryk Kopczyński
def find_shortest_path(graph, start, end):
dist = {start: [start]}
q = deque(start)
while len(q):
at = q.popleft()
for next in graph[at]:
if next not in dist:
dist[next] = [dist[at], next]
q.append(next)
return dist.get(end)
請注意，這將以奇怪的格式返回路徑，例如，[[['A'], 'B'], 'D']。特別是，len(find_shortest_path(graph, 'A', 'D')) 將給出不正確的答案（2，因為外部列表的長度為 2）。這是因為 append 是作為 [dist[at], next] 而不是 dist[at]+[next] 完成的。第二種方法會使用二次時間和記憶體，但對於相對較小的圖來說應該還是可以的；否則，很容易將列表轉換為正確的格式。另一種變體是新增更多資料抽象：建立一個類來表示圖，其方法實現各種演算法。雖然這符合結構化程式設計的願望，但它不會使程式碼更高效（相反）。它確實可以更輕鬆地向節點或弧新增各種標籤，並新增考慮這些標籤的演算法（例如，查詢地圖上兩個城市之間的最短路線）。這也將是另一篇專欄的主題。