在{1,2,3}中爲邊緣權重尋找最小生成樹的算法

我最近一直在研究在Prims/Kruskals算法中尋找圖表中的最小生成樹，我對以下問題感興趣：在{1,2,3}中爲邊緣權重尋找最小生成樹的算法

10設G是一個有m條邊的n個頂點的無向圖，這樣每條邊的權值爲w（e）∈{1,2,3}。是否有一種算法在時間O（n + m）中找到G的最小生成樹？

顯然，您可以在圖上運行Prims，並且您會得到一個最小生成樹，但不會在所需的時間。

我想，我們可以通過增加每邊緣具有重量1到樹開始，只要它不產生循環，因爲如果存在不產生週期重量1的邊緣，然後將其優選的邊緣重量2說，並按順序進行。

任何有關設計算法的可能方法的幫助將不勝感激，任何實現（Java更可取，但歡迎任何語言）將是超級有用的。

來源

2016-02-25 mathcomp

您正在描述克魯斯卡爾算法的一個小變體，該算法使得按m的邊重量O（m）進行排序的代價很高，因爲您只需要將邊放入3個桶中。

由於Kruskal的其餘部分非常接近O（m），由於disjoint set data structure的驚人屬性，您應該保持良好狀態。

構建樹本身應該是O（m）而不是O（n + m），因爲不需要處理頂點。例如。如果你在一個gazillion頂點上有幾條邊，大多數沒有連接，那麼如果你仔細考慮數據結構的設計，後者不需要增加算法成本。

來源

2016-02-25 18:24:22 Gene

謝謝你。我現在已經明白，我只能適應Kruskals並具備以下條件：使用聯盟查找（不相交集）的數據結構：對於V所有V，MAKE_SET（V）; 將非遞減順序的邊排序爲3個桶（每個桶對應一個特定的邊權重）;對於E中的每個邊（u，v），從桶1中的每個邊（u，v）開始（即，以非遞減順序）如果FIND（u）！= FIND（v）則T = T U（u，v）; UNION（u，v）; } 回報T – mathcomp

這個工作在O（m + n）時間嗎？如果沒有，你能幫助我誤解/提供一些僞代碼嗎？對不起，如果我不明白 – mathcomp

它工作在O（alpha（m））時間。對於已知宇宙中的任何目的，alpha（m）<5m。所以在實踐中它是O（m）。你的描述很好。「分類」不是傳統意義上的。只有一次通過元素在固定時間內分配給右桶。 @mathcomp – Gene

在{1,2,3}中爲邊緣權重尋找最小生成樹的算法

回答

相關問題