广度优先搜索算法

2 回答

• 0

  您的代码中存在许多问题 -

  • 首先，您永远不会在您创建的队列中放置任何内容，因此它始终为空，您需要在 while 循环之前将 v 放入队列中，这是起点 .

  • 其次，在 for 循环中，您正在检查 element == 0 ，这是错误的，您需要检查是否 graphv[element] == 0 ，即元素是否已被访问过 .

  • 第三，在 for 循环中，您需要设置 graphv[element] = count ，表示您已经生效 element .

  • 您没有使用 - visited.put() 将任何内容放入队列中，您需要将该元素作为参数传递到Queue内部 .

  • 从队列中取回元素时，需要将其分配回 v ，否则 v 永远不会改变， v 表示当前正在迭代的元素 .

  示例代码 -

  import sys
  import Queue
  
  # Input has to be adjacency matrix or list
  graphAL2 = {0 : [1,2,3],
          1 : [0,3,4],
          2 : [0,4,5],
          3 : [0,1,5],
          4 : [1,2],
          5 : [2,3] }
  
  # NEED TO FIX:
  # - Final graphAL2v print is only displaying key values as 1, not iterating
  # through graph and visiting each vertex
  
  def main():
      count = 0
      graphAL2v = {}
  
      for key, value in graphAL2.items():
          graphAL2v[key] = 0
  
      print(graphAL2v)
  
      for key in graphAL2v: # each vertex v in V
          if graphAL2v[key] == 0: # is marked with 0
              bfs(key, count, graphAL2, graphAL2v)
      print(graphAL2v)
  
  def bfs(v, count, graphal, graphv):
      count = count + 1
      print('Visiting', v)
  
      # Mark v with count and initialize queue with v
      graphv[v] = count
      visited = Queue.Queue()
      visited.put(v)
      while not visited.empty(): #queue not empty:
          print('queue is not empty')
          for element in graphal[v]: # each vertex w in V adjacent to front vertex
              if graphv[element] == 0:
                  count = count + 1
                  # mark w with count
                  graphv[element] = count
                  visited.put(element)
          v = visited.get()
      return count
  
  if __name__ == '__main__':
      sys.exit(main())
  

  ---

  演示（经过上述变更） -

  {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
  Visiting 0
  queue is not empty
  queue is not empty
  queue is not empty
  queue is not empty
  queue is not empty
  queue is not empty
  {0: 1, 1: 2, 2: 3, 3: 4, 4: 5, 5: 6}
  

  回复于 2024-05-21T16:00:05+08:00
• 3

  您可以使用提供搜索算法的图库之一，例如NetworkX：

  from networkx import *
  graphAL2 = {0 : [1,2,3],
          1 : [0,3,4],
          2 : [0,4,5],
          3 : [0,1,5],
          4 : [1,2],
          5 : [2,3] }
  
  g = Graph()
  
  # create graph
  for node in graphAL2:
      g.add_node(node)
      for target_node in graphAL2[node]:
          g.add_edge(node, target_node)
  
  print bfs_successors(g, 0)
  

  这将获得每个节点的后继者，从中导出搜索顺序应该是小菜一碟 .

  输出：

  {0: [1, 2, 3], 1: [4], 2: [5]}
  

  回复于 2024-05-21T16:00:05+08:00