Python 模式 - 實現圖
警告
此頁面因歷史原因保留，可能包含過時或不正確的資訊。
find_shortest_path 為“接近最優”。2019年8月11日：修復了意外使用 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 指出這些函式並非最優。相反，“這個程式以指數時間執行，而 find_shortest_path 可以使用 BFS [廣度優先搜尋] 以線性時間完成。此外，線性 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] 完成的。第二種方法將使用二次時間和記憶體，但對於相對較小的圖應該仍然可以；否則，很容易將列表轉換為正確的格式。另一種變體是新增更多資料抽象：建立一個類來表示圖，其方法實現各種演算法。雖然這吸引了對結構化程式設計的渴望，但它並不能使程式碼更有效率（相反）。它確實使向節點或弧新增各種標籤以及新增考慮這些標籤的演算法變得更容易（例如，在地圖上查詢兩個城市之間的最短路線）。這也將是另一個專欄的主題。