圖的 最小生成樹算法 原理簡介：Prim’s algorithm and Kruskal’s algorithm

文章目錄

• Graph
• • Minimum Spanning Tree（最小生成樹)）
  • • 生成算法
    • • 1. Prim's algorithm（ 普林演算法 ）
      • • 實作
        • 與 Dijkstra 的差異
      • 2.Kruskal's algorithm（克魯斯卡爾算法）
      • • 實作

Graph

Minimum Spanning Tree（最小生成樹)）

定義：For an undirected graph G，is a tree formed from graph edges that：

① connects all the vertices of G ② at lowest total cost.

存在性：MST exists iff G is connected.

graph G	MST

生成算法

Prim’s algorithm（ 普林演算法 ）	Kruskal’s algorithm（克魯斯卡爾算法）
定義	首先以某一節點當作出發點，加入到樹 T 内。 LOOP：在與樹 T 鄰接的樹外（尚未被選取的）節點 E 中，選擇到樹 T 的邊權重最小的節點 e， 將 e 和相應邊加入 T。 UNTIL：增加了n - 1條邊為止。(假設有 n 個節點)	首先邊的權重從小到大排序。 依次判斷是否需要該邊。要求加入該邊後不會形成回路。
特性	貪心算法（局部最優） 不斷擴張某一棵樹	貪心算法（資源排序） 最開始所有點都看成是樹，其過程就是不斷連接配接森林裡面的各棵樹 •maintains a forest—a collection of trees. •Initially, there are single-node trees. Adding an edge merges two trees into one. •When the algorithm terminates, there is only one tree.

1. Prim’s algorithm（ 普林演算法 ）

實作

下表中，known 标志樹内外節點 ，dv 标記該節點到樹 T 的最小邊權重，pv 記錄其父節點。

1. 将節點 v1 作為 root 加入到樹 T 中，更新鄰接的樹外點到樹 T 的距離，即 v2、3、4 到 v1 的邊權重。

   選擇鄰接邊中權重最小的節點 v4 将其加入到 T 中，即：将 known（v4）= T，pv（v4）= v1。

1. 重複：将 v2 加入到 T 中，更新鄰接于 v4 的樹外點到樹 T 的距離，例如 v3 與 v2 的距離比 v1 更近，是以dv（v3）= 2，pv（v3）= v2。

   選擇鄰接邊中權重最小的節點 v2、3 将其加入到 T 中。

1. 重複：将 v2、3 加入到 T 中，更新鄰接于 v2、3 的樹外點到樹 T 的距離。

   選擇鄰接邊中權重最小的節點 v7 将其加入到 T 中。

1. 重複：将 v7 加入到 T 中，更新鄰接于 v7 的樹外點到樹 T 的距離。

   選擇鄰接邊中權重最小的節點 v6 加入到 T 中。

1. 重複 UNTIL：增加了n - 1條邊為止。(假設有 n 個節點)

與 Dijkstra 的差異

唯一差異：如何更新 dv

假設 w 為已知點，v 為未知點

• Dijkstra: dv=min{dv, dw+c(w,v)} 其中 dv、w的含義是由源點到 v、w的路徑和
• Prim: dv=min{dv, c(w,v)} 其中 dv、w的含義是到樹中父節點的距離，如果 dv=c(w,v) 成立，則v的父節點修改為w

2.Kruskal’s algorithm（克魯斯卡爾算法）

實作

先将邊按 權重 從小到大排序，然後依次取邊，注意如果加入該邊會形成回路時，要reject掉。