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