Python - 图形算法

---

---

图形是解决许多重要数学挑战的非常有用的数据结构。例如，计算机网络拓扑或分析化合物的分子结构。它们还用于城市交通或路线规划，甚至用于人类语言及其语法。所有这些应用程序都有一个共同的挑战，即使用它们的边缘遍历图形并确保访问图形的所有节点。有两种常见的既定方法可以进行此遍历，如下所述。

深度优先遍历

也称为深度优先搜索 （DFS），此算法以深度向运动遍历图形，并使用堆栈来记住在任何迭代中出现死胡同时获取下一个顶点以开始搜索。我们使用 set 数据类型在 python 中为图形实现 DFS，因为它们提供了跟踪已访问和未访问节点所需的功能。

例

class graph:
	 	def __init__(self,gdict=None):
	 	 	 if gdict is None:
	 	 	 	 	gdict = {}
	 	 	 self.gdict = gdict
# 检查已访问和未访问的节点
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')

输出

执行上述代码时，它会产生以下结果 -

广度优先遍历

也称为广度优先搜索 （BFS），该算法遍历图广度向运动，并使用队列来记住在任何迭代中出现死胡同时获取下一个顶点以开始搜索。请访问我们网站上的此链接，了解图表的 BFS 步骤的详细信息。

我们使用前面讨论的队列数据结构在 python 中为图形实现 BFS。当我们不断访问相邻的未访问节点并继续将其添加到队列中时。然后，我们开始仅取消排队没有未访问节点的节点。当没有下一个要访问的相邻节点时，我们将停止程序。

例

import collections
class graph:
	 	def __init__(self,gdict=None):
	 	 	 if gdict is None:
	 	 	 	 	gdict = {}
	 	 	 self.gdict = gdict
def bfs(graph, startnode):
# 使用队列跟踪已访问和未访问的节点
	 	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)

# 图形词典
gdict = {	
	 	"a" : set(["b","c"]),
	 	"b" : set(["a", "d"]),
	 	"c" : set(["a", "d"]),
	 	"d" : set(["e"]),
	 	"e" : set(["a"])
}
bfs(gdict, "a")

输出

执行上述代码时，它会产生以下结果 -