1
我得到了一個無向圖,使所有具有相同權重的邊與所有頂點相連。我想找到任何給定的頂點對之間的路徑。查找無向圖中任意兩個節點之間路徑的有效方法
效率較低的解決方案是: 要從其中一個頂點開始執行BFS,請跟蹤訪問的頂點,直到達到目標頂點。這將在O(V + E)中執行。但是這必須爲給定的每一對頂點完成。因此,如果有M個查詢來查找路徑,則複雜度將是O(M *(E + V))。
我們可以做得更好嗎?是否有可能利用輸出BFS並解決其餘問題?