Python 中的广度优先搜索 (BFS) 用于遍历路径和采用的最短路径

Question

我尝试了很多次，但就是不明白。起始节点是 S，目标节点是 J。我只是根本没有得到 J。

这是我用于遍历路径的代码，但我还需要找到最短路径

graph = {
  'S' : ['A','B', 'C'],
  'A' : ['D'],
  'B' : ['E'],
  'C' : ['F', 'J'],
  'D' : ['G'],
  'E' : ['I', 'J'],
  'F' : ['S'],
  'J' : [],
  'G' : ['H'],
  'I' : [],
  'J' : [],
  'H' : ['D']
}

visited = [] # List for visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node): #function for BFS
  visited.append(node)
  queue.append(node)

  while queue:          # Creating loop to visit each node
    m = queue.pop(0) 
    print (m, end = " ") 

    for neighbour in graph[m]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, 'S')    # function calling

Answer 1

您需要告诉 BFS 函数您的目标节点是什么，以便 BFS 遍历在遇到该目标节点时立即停止。

其他一些评论：

• 你的字典文字有一个重复的键“J”——你应该删除它

• visited

  和

  queue

  仅服务于单个 BFS 调用，并且每次启动 BFS 搜索时都应从头开始。所以这些不应该是全局名称，而只能在函数范围内定义。

• 您可以在访问节点时打印它们，但这并不代表路径。它表示图的level顺序遍历。所以不要打印这个。相反，让函数返回路径（参见下一点）

• visited

  很有趣，可以避免一遍又一遍地重新访问同一个节点，但它没有提供有关我们如何到达某个节点的信息。您可以将

  visited

  更改为字典。然后，当您将节点标记为已访问时，请使用您来自的节点来标记它。这样，一旦找到目标节点，您就可以重建路径——您可以向后走回到起始节点。

• 您已将队列定义为列表，但列表的

  pop(0)

  方法调用效率不高。相反，请使用

  deque

  及其

  popleft()

  方法。

这是您的代码，考虑了上述注释。

from collections import deque

graph = {
  'S' : ['A','B', 'C'],
  'A' : ['D'],
  'B' : ['E'],
  'C' : ['F', 'J'],
  'D' : ['G'],
  'E' : ['I', 'J'],
  'F' : ['S'],
  'G' : ['H'],
  'I' : [],
  'J' : [],
  'H' : ['D']
}

def bfs(graph, node, target):
    # These lists should not be global. At each call of BFS, they should reset
    visited = {}  # Use a dict so you can store where the visit came from
    queue = deque()    # Use a deque to not lose efficiency with pop(0)

    visited[node] = None
    queue.append(node)
    
    while queue:
        m = queue.popleft() 
        if m == target:  # Bingo!
            # Extract path from visited information
            path = []
            while m:
                path.append(m)
                m = visited[m]  # Walk back
            return path[::-1]  # reverse it
        for neighbour in graph[m]:
            if neighbour not in visited:
                visited[neighbour] = m  # Remember where we came from
                queue.append(neighbour)
                
# Driver Code
print("Following is the Breadth-First Search")
print(bfs(graph, 'S', 'J'))

输出：

['S', 'C', 'J']