2016-08-31 61 views
1

我得到了一個無向圖,使所有具有相同權重的邊與所有頂點相連。我想找到任何給定的頂點對之間的路徑。查找無向圖中任意兩個節點之間路徑的有效方法

效率較低的解決方案是: 要從其中一個頂點開始執行BFS,請跟蹤訪問的頂點,直到達到目標頂點。這將在O(V + E)中執行。但是這必須爲給定的每一對頂點完成。因此,如果有M個查詢來查找路徑,則複雜度將是O(M *(E + V))。

我們可以做得更好嗎?是否有可能利用輸出BFS並解決其餘問題?

回答

0

當您聲明圖形已連接時,不需要多次調用該圖形的搜索算法。使用對BFS(或DFS,這應該沒有什麼重大區別)的單個調用來爲輸入生成生成樹就足夠了。從您的問題聲明它顯然沒有必要找到頂點之間的最短路徑,任何對頂點(a,b)通過路徑連接從a到根生成樹rrb的路徑。

運行時將是O(V+E),即te搜索算法的運行時間;爲生成實際路徑本身可能需要額外的計算成本。

相關問題