使用最小生成樹查找從A到B的路徑 - C/C++

假設我們找到最小生成樹。現在，我們只需要在MST中從A到Z的路徑。我們如何在O（n^2）時間內做到這一點？使用最小生成樹查找從A到B的路徑 - C/C++

我們從根A開始，然後我們查看Ax形式的樹（其中x是任何頂點）中的所有邊。

然後，說我們找到：AB，AC，AD等...... 然後對於每一個，我們尋找形式的邊：Bx，Cx，Dx ...這顯然不是O（n^2 ）。

那麼什麼是更好/有效的方式來找到路徑A - > Z給定MST？

由於

2012-07-09 user809240

DFS就足夠了 – user1168577 2012-07-09 16:05:37

邊權重是點之間的距離，所以不是它們不一定是整數。 – user809240 2012-07-09 16:07:38

DFS如何工作？我們從MST創建一個DFS？ – user809240 2012-07-09 16:08:13

Depth-first search將是足夠的，它是在最壞情況下O（| V | + | E |）。事實上，你的輸入是一個MST意味着你不必擔心任何循環檢測，就像你在一般的圖表中一樣。

2012-07-09 16:13:28

也應該注意，在MST中'| E |'最多是'| V |'而不是在一般圖中的| V |^2，所以算法將是'O（| V |）'。比'O（| V |^2）'的目標快得多。 – JPvdMerwe 2012-07-09 17:04:36

查找Minimum Spanning Tree，你會發現它是一個連接所有頂點的最小子圖。這意味着每個邊緣將被用於大部分一次。您可以使用DFS或BFS來查找所需的路徑，而無需檢查週期，因爲您已經擁有MST。

2012-07-09 16:14:32 NominSim

在MST創建過程中，您可以填充父項[]，因此在使用簡單的回溯後，您將能夠找到沒有DFS的路徑。

2012-07-09 18:03:16

如果你仔細想想，Prim找到MST的算法實際上只是Dijkstra的僞裝。因此，如果您找到一個MST，就可以爲您提供最短路徑（如上所述，請考慮DFS）。

2012-07-09 18:12:51 tskuzzy

回答