Java 資料結構 - 克魯斯卡爾演算法

克魯斯卡爾演算法用於尋找最小生成樹，它使用貪心策略。該演算法將圖視為森林，並將每個節點視為一棵獨立的樹。一棵樹只能連線到另一棵樹，當且僅當它在所有可用選項中成本最低且不違反 MST 屬性時。

為了理解克魯斯卡爾演算法，讓我們考慮以下示例 -

步驟 1 - 刪除所有環和並行邊

從給定的圖中刪除所有環和並行邊。

如果存在並行邊，保留關聯成本最低的那條邊，並刪除所有其他邊。

步驟 2 - 按權重遞增順序排列所有邊

下一步是建立一個邊和權重的集合，並按權重（成本）升序排列它們。

步驟 3 - 新增權重最小的邊

現在我們開始從權重最小的邊開始向圖中新增邊。在整個過程中，我們將持續檢查生成樹屬性是否保持不變。如果透過新增一條邊，生成樹屬性不成立，那麼我們將考慮不將該邊包含在圖中。

最小成本是 2，涉及的邊是 B,D 和 D,T。我們新增它們。新增它們不會違反生成樹屬性，因此我們繼續選擇下一條邊。

下一個成本是 3，相關的邊是 A,C 和 C,D。我們再次新增它們 -

表中的下一個成本是 4，我們觀察到新增它將在圖中建立一個迴路。

我們忽略它。在此過程中，我們將忽略/避免所有建立迴路的邊。

我們觀察到成本為 5 和 6 的邊也會建立迴路。我們忽略它們並繼續。

現在我們只剩下一個節點需要新增。在兩個可用的最小成本邊 7 和 8 之間，我們將新增成本為 7 的邊。

透過新增邊 S,A，我們已經包含了圖的所有節點，並且現在我們有了最小成本生成樹。