Python Data Structure 简明教程
Python - Graph Algorithms
图是非常有用的数据结构，可用于解决许多重要的数学难题。例如，计算机网络拓扑或分析化学化合物的分子结构。它们还用于城市交通或路线规划，甚至用于人类语言及其语法。所有这些应用程序都有一个共同的挑战，即使用图的边遍历图并确保访问图的所有节点。有两种常见的已建立的方法来执行此遍历，如下所述。
Depth First Traversal
也称为深度优先搜索 (DFS)，此算法以深度向运动遍历图，并使用栈来记住在任何迭代中发生死锁时获取下一个顶点以开始搜索。我们使用集合数据类型为 python 中的图实现 DFS，因为它们提供了跟踪已访问和未访问节点所需的功能。
Example
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
gdict = {
"a" : set(["b","c"]),
"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
dfs(gdict, 'a')Breadth First Traversal
也称为广度优先搜索 (BFS)，此算法以广度向运动遍历图，并使用队列来记住在任何迭代中发生死锁时获取下一个顶点以开始搜索。请访问我们网站上的此链接以了解图的 BFS 步骤的详细信息。
我们在 Python 中使用前面讨论过的队列数据结构来实现图的 BFS。当我们持续访问相邻未访问的节点并将它们添加到队列中时。然后我们仅对没有未访问节点的节点开始出队。当没有相邻节点要访问时，我们停止程序。
Example
import collections
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
seen, queue = set([startnode]), collections.deque([startnode])
while queue:
vertex = queue.popleft()
marked(vertex)
for node in graph[vertex]:
if node not in seen:
seen.add(node)
queue.append(node)
def marked(n):
print(n)
# The graph dictionary
gdict = {
"a" : set(["b","c"]),
"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
bfs(gdict, "a")