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] 完成的。第二种方法会使用二次时间和内存，但对于相对较小的图来说应该还是可以的；否则，很容易将列表转换为正确的格式。另一种变体是添加更多数据抽象：创建一个类来表示图，其方法实现各种算法。虽然这符合结构化编程的愿望，但它不会使代码更高效（相反）。它确实可以更轻松地向节点或弧添加各种标签，并添加考虑这些标签的算法（例如，查找地图上两个城市之间的最短路线）。这也将是另一篇专栏的主题。