Python Data Structure 简明教程
Python - Graph Algorithms
图是非常有用的数据结构，可用于解决许多重要的数学难题。例如，计算机网络拓扑或分析化学化合物的分子结构。它们还用于城市交通或路线规划，甚至用于人类语言及其语法。所有这些应用程序都有一个共同的挑战，即使用图的边遍历图并确保访问图的所有节点。有两种常见的已建立的方法来执行此遍历，如下所述。
Graphs are very useful data structures in solving many important mathematical challenges. For example computer network topology or analysing molecular structures of chemical compounds. They are also used in city traffic or route planning and even in human languages and their grammar. All these applications have a common challenge of traversing the graph using their edges and ensuring that all nodes of the graphs are visited. There are two common established methods to do this traversal which is described below.
Depth First Traversal
也称为深度优先搜索 (DFS)，此算法以深度向运动遍历图，并使用栈来记住在任何迭代中发生死锁时获取下一个顶点以开始搜索。我们使用集合数据类型为 python 中的图实现 DFS，因为它们提供了跟踪已访问和未访问节点所需的功能。
Also called depth first search (DFS),this algorithm traverses a graph in a depth ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration. We implement DFS for a graph in python using the set data types as they provide the required functionalities to keep track of visited and unvisited nodes.
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 步骤的详细信息。
Also called breadth first search (BFS),this algorithm traverses a graph breadth ward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration. Please visit this link in our website to understand the details of BFS steps for a graph.
我们在 Python 中使用前面讨论过的队列数据结构来实现图的 BFS。当我们持续访问相邻未访问的节点并将它们添加到队列中时。然后我们仅对没有未访问节点的节点开始出队。当没有相邻节点要访问时，我们停止程序。
We implement BFS for a graph in python using queue data structure discussed earlier. When we keep visiting the adjacent unvisited nodes and keep adding it to the queue. Then we start dequeue only the node which is left with no unvisited nodes. We stop the program when there is no next adjacent node to be visited.
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")