查找MST的所有關鍵邊緣

Question

我從Robert Sedgewick的算法書中得到了這個問題。

關鍵邊緣。從圖中刪除會導致MST權重增加的MST邊稱爲臨界邊。顯示如何在與E log E成比例的時間內查找所有關鍵邊的時間。注意：此問題假設邊緣權重 不一定是不同的（否則MST中的所有邊都是關鍵的）。

請提出解決此問題的算法。

我能想到的一種方法是在時間上做這項工作E.V. 我的方法是運行kruskal的算法。但是，無論何時我們遇到在MST中插入的邊創建一個循環，並且如果該循環已經包含具有相同邊權重的邊，那麼已插入的邊將不是關鍵邊（否則所有其他MST邊緣是關鍵邊緣）。

該算法是否正確？如何擴展此算法以便及時完成作業E日誌E.

Answer 1

是的，您的算法是正確的。我們可以證明，通過將Kruskal算法的執行情況與某些MST邊e的成本更改爲無窮大的類似執行進行比較。在第一次執行考慮e之前，兩個執行都是相同的。在e之後，第一次執行的連接組件少於第二個。這種情況一直存在，直到邊e'被認爲是在第二次執行時加入了會有的組件。由於e邊是目前構建的森林之間的唯一區別，它必須屬於由e'創建的循環。在e'之後，執行者做出相同的決定，森林中的差異是第一次執行有e，第二次執行e'。

實現此算法的一種方法是使用動態樹，這是一種代表標記森林的數據結構。此ADT的一種配置在對數時間中支持以下方法。

• MakeVertex（） - 構造並返回一個新的頂點。
• 鏈接（u，c，v） - 頂點u和v不能連接。以成本c創建從頂點u到頂點v的未標記邊。 Mark（u，v） - 頂點u和v必須是邊e的端點。標記e。
• 連接（u，v） - 指示頂點u和v是否連接。
• FindMax（u，v） - 頂點u和v必須連接。返回從u到v的唯一路徑上的未標記邊的端點，其成本最高，並返回該成本。該邊緣的端點按它們出現在路徑上的順序給出。

我不認爲這是一個很好的算法在實踐中。像瑞士軍刀這樣的動態樹木是多功能但複雜的，而且往往不是這項工作的最佳工具。我鼓勵你考慮如何利用這個事實，即我們可以等待所有的邊被處理，以確定關鍵邊是什麼。

Answer 2

你認爲當邊緣很危險的時候你的狀況是正確的，我想。但沒有必要真正找到一個週期並測試它的每個邊緣。

克魯斯卡爾算法增加了邊緣的增加重量順序，所以邊緣添加的序列可以分解成等重邊添加塊。在每個等重塊內，如果有多於一條邊連接相同的兩個分量，那麼所有這些邊都是非關鍵的，因爲可以選擇任何一個其他邊。 （我說他們是全部非關鍵因爲我們實際上沒有給出特定的MST作爲輸入的一部分 - 如果我們這樣做，那麼這將確定一個特殊的邊界來稱爲非關鍵邊緣.Kruskal實際選擇的邊緣是隻是初始邊緣排序的一種假象或者排序是如何實現的）。

但是這還不夠：它可能是在向MST添加權重4或更小的所有邊之後，我們發現有3個權重 - 5個邊，連接組件對（1,2），（2,3）和（1,3）。雖然沒有任何組件對通過這3個邊中的1個以上連接，但我們只需要（任何）2個 - 使用全部3個會創建一個循環。

對於每個有權重w的等權塊，我們實際需要做的是（概念上）創建一個新圖，其中MST的每個分量到目前爲止（即使用重量爲< w的邊）是頂點，並且每當在這些組件之間存在權重w邊緣時，在2個頂點之間存在邊緣。 （這可能會導致多邊形。）然後，我們在此圖形的每個組件上運行DFS以查找任何週期，並將屬於此週期的每條邊標記爲非關鍵。 DFS需要O（nEdges）時間，因此每個塊（其大小總和爲E）的DFS時間總和將爲O（E）。

請注意，克魯斯卡爾算法需要花費時間O（Elog E），而不是O（E），雖然像Bernard Chazelle這樣的人已經接近線性時間MST構造，但TTBOMK還沒有人！ :)