爲什麼不能在有向圖上使用Prim's或Kruskal的算法？

Question

Prim's和Kruskal的算法用於查找已連接和未連接的圖的最小生成樹。爲什麼他們不能用在一個指向的圖表上？

Answer 1

這些算法首先起作用是一個小小的奇蹟 - 大多數貪婪算法只是在某些情況下發生崩潰和燒燬。假設你想使用它們來找到一個最小跨度樹狀結構（從一個頂點到所有其他頂點的有向路徑），那麼Kruskal的一個有問題的圖看起來像這樣。

5 
    --> a 
//^ 
s 1| |2 
\ v/
    --> b 
3 

我們將採用A->成本1的B圓弧，然後會被卡住，因爲我們真的想S-> b成本3和B-> A成本的2

對於普里姆，這個圖是有問題的。

5 
    --> a 
//
s 1| 
\ v 
    --> b 
3 

我們將採取S-> b成本3的，但我們真的想S->成本5和A->說明B成本的1

Answer 2

普里姆的和Kruskal算法輸出最小生成樹連接和「無向」圖。如果它沒有連接，我們可以調整它們以輸出最小生成森林。

在Prim的算法中，我們將圖分成兩組頂點。一組已經形成MST的探索頂點（Set1）和另一組未開發的頂點將最終加入第一組以完成「跨越」（Set2）。在每一瞬間，我們選擇加入兩個不相交集合的切割中的最小加權邊緣。如果沒有從MST的探索節點到剩餘的未探索節點的有向邊，即使存在從未探索節點到MST中探索節點的邊，算法仍然卡住。

在Kruskal算法中，其思想是按照它們的權重按升序對邊進行排序，並按順序挑選它們，並將它們包括在MST探索的節點/邊中，前提是它們不能與探索節點形成循環。這由Union-Find DS完成。但是使用這種方法檢測有向圖的循環失敗。例如：包含邊[1-> 2] [2-> 3] [1-> 3]的圖將被報告包含使用Union-Find方法的循環。

因此，Prim的失敗，因爲它假設，每個節點都可以從每個節點到達，儘管有效的無向圖可能不適用於有向圖。克魯斯卡爾失敗是因爲未能檢測到週期，有時候必須增加邊緣週期以滿足MST的「最小」加權屬性。

此外，在有向圖的情況下，MST沒有完全意義。它與二叉樹的等價物是「最小跨度樹狀結構」，它將產生一棵樹，每個頂點可以從一個頂點到達。