Python - 图形算法

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

深度优先遍历

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

示例

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')

输出

当上面的代码执行时，会产生如下结果 −

a 
b 
d 
e 
c

广度优先遍历

也称为广度优先搜索（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):
# 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")

输出

当上面的代码执行时，会产生如下结果 −

a 
c 
b 
d 
e