Python：廣度優先搜索能夠返回最大距離嗎？

Question

我有一個代表有向圖的字典。例如...

​​3210

這意味着「富」節點指向「你好」和「棧」而「酒吧」節點指向「上方」和'流'。

我也寫代碼，首先進行廣度搜索，查找任何兩個節點之間的最短路徑 ...

from collections import deque 

def breadthFirstSearch(graph, start, end): 
    q = deque() 
    path = (start,) 
    q.append(path) 
    visited = set([start]) 
    while q: 
     path = q.popleft() 
     last_node = path[-1] 
     if last_node == end: 
      return path 
     for node in graph[last_node]: 
      if node not in visited: 
       visited.add(node) 
       q.append(path + (node,)) 
    print 'There is no path from ' + start + ' to ' + end + '.' 
    return None 

我的問題是：是否有可能修改該廣度優先搜索等等因爲它給了我最大的最短路徑以及該路徑的開始和結束節點？

Answer 1

你的問題叫做「圖形直徑問題」。

廣度優先搜索創建廣度優先搜索樹。由於非樹邊緣的存在，兩個節點之間最長的樹通常會比它們之間的最長路徑長。所以不，你不能讓BFS直接做到這一點。

BFS會將它釘在樹上，但它略顯不平凡。

有一個名爲「字典寬度優先搜索」的變體，可以找到某些受限類圖的直徑。那些我在LBFS中運行的圖類往往看起來很像樹。

編輯：當然，您可以從每個節點開始運行BFS，並計算出BFS報告的最長路徑。或者你可以使用非常優雅的Floyd-Warshall algorithm。