上一节:
下一节:

  Python - 算法之图算法

  • 简述

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

  • 深度优先遍历

    也称为深度优先搜索 (DFS)，该算法以深度 ward 运动遍历图，并在任何迭代中出现死胡同时，使用堆栈记住获取下一个顶点以开始搜索。我们使用集合数据类型在 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)，该算法遍历图广度 ward 运动并使用队列记住在任何迭代中出现死胡同时获取下一个顶点以开始搜索。请访问我们网站中的此链接以了解图表的 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
上一节:
下一节: