Python数据结构图形算法

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

深度优先遍历法

这种算法也被称为深度优先搜索（DFS），它以深度扫描的方式遍历图形，当任何迭代中出现死胡同时，使用一个堆栈来记住获得下一个顶点来开始搜索。我们在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")