广度优先搜索和路径遍历问题

Question

I'm not getting J as my goal node in 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']
}

我需要找到所采取的最短路径以及经过的路径。

Answer 1

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

其他一些评论：

• 你的字典文字有一个重复的键

  'J'

  ——你应该删除它。

• visited

  和

  queue

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

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

• 列表

  visited

  用于避免再次重新访问同一节点，但它不会为您提供有关我们如何到达某个节点的任何信息。您可以将

  visited

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

• 您已将

  queue

  定义为列表，但列表的

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

如果您想查看哪些节点被访问，那么您有一些选择：

• 显示节点何时从队列中出队：

  改变：

  m = queue.popleft() 
  

  至：

  m = queue.popleft() 
  print (m, end = " ") 
  

  或：

• 显示节点何时入队：

  改变：

  queue.append(neighbour)
  

  至：

  queue.append(neighbour)
  print (neighbor, end = " ") 
  

  并更改：

  改变：

  queue.append(node)
  

  至：

  queue.append(node)
  print (node, end = " ") 
  

输出略有不同，这取决于您所说的“访问”。第二个将输出另外两个永远不会从队列中弹出的节点。

要将访问的输出与路径的输出分开，只需使用

print()

打印换行符即可。因此，在驱动程序代码中执行以下操作：

path = bfs(graph, 'S', 'J'))
print()  # Extra print to start a new line
print(path)