離散數學 - 生成樹

---

---

連通無向圖 $G$ 的生成樹是指包含 $G$ 中所有頂點的最小連通子圖。一個圖可能有多個生成樹。

示例

最小生成樹

對於一個加權的、連通的、無向圖 $G$，如果一個生成樹的權重小於或等於該圖所有可能的生成樹的權重，則稱之為最小生成樹 (MST)。生成樹的權重是指生成樹中所有邊的權重之和。

示例

克魯斯卡爾演算法

克魯斯卡爾演算法是一種貪心演算法，用於尋找連通加權圖的最小生成樹。它找到該圖中包含每個頂點的樹，並且樹中所有邊的總權重小於或等於所有可能的生成樹。

演算法

步驟 1 - 將給定圖 $G (V,E)$ 的所有邊按其邊權重升序排列。

步驟 2 - 從圖中選擇權重最小的邊，並檢查它是否與迄今為止形成的生成樹構成環。

步驟 3 - 如果沒有環，則將此邊包含到生成樹中，否則丟棄它。

步驟 4 - 重複步驟 2 和步驟 3，直到生成樹中剩下 $(V-1)$ 條邊。

問題

假設我們想使用克魯斯卡爾演算法為以下圖 G 找到最小生成樹。

解決方案

根據上圖，我們構建以下表格 -

現在我們將表格根據邊權重升序重新排列 -

由於我們在上圖中得到了所有 5 條邊，因此我們停止演算法，這就是最小生成樹，其總權重為 $(1 + 2 + 3 + 5 + 9) = 20$。

普里姆演算法

普里姆演算法由數學家沃伊捷赫·亞爾尼克和羅伯特·C·普里姆於 1930 年發現，是一種貪心演算法，用於尋找連通加權圖的最小生成樹。它找到該圖中包含每個頂點的樹，並且樹中所有邊的總權重小於或等於所有可能的生成樹。普里姆演算法在稠密圖上速度更快。

演算法

• 用從圖中隨機選擇的單個頂點初始化最小生成樹。

• 重複步驟 3 和 4，直到所有頂點都被包含在樹中。

• 選擇一條連線樹與尚未在樹中的頂點的邊，使得邊的權重最小，並且邊的包含不會形成環。

• 將所選邊及其連線到的頂點新增到樹中。

問題

假設我們想使用普里姆演算法為以下圖 G 找到最小生成樹。

解決方案

這裡我們從頂點 'a' 開始並繼續。

這是最小生成樹，其總權重為 $(1 + 2 + 3 + 5 + 9) = 20$。