最小生成樹
定義
生成樹：無向圖中，包含所有定點在內的極小連通子圖
最小生成樹：
在一給定的無向圖G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊（即），而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集且為無回圈圖，使得聯通所有結點的的 w(T) 最小，則此 T 為 G 的最小生成樹，
最小生成樹其實是最小權重生成樹的簡稱
最小生成樹問題：
-
A Generic Algorithm
-
具有貪心選擇性：
- Kruskal's Algorithm
- Prim's Algorithm
最小生成樹需具備的條件：
-
Tree is an acyclic（無環），connected(連通、無向) graph.
-
A tree of |V| vertices has |V| - 1 edges.
-
并且任何兩個頂點存在unique（唯一的）路徑
-
增加任何一條邊都會使得樹形成回路，如果去掉任何一條邊，就會使得該樹不再連通
問題
輸入：一個連通帶權無向圖G(V，E；W)
輸出：一個最小生成樹T for G
方法
A Generic Algorithm
- 每次生成最小生成樹的一條邊：須遵循，在一次回圈之前，集合A已經是最小生成樹的子集的原則
- 安全邊：A如果加上{（u，v）}這條邊和相關頂點以后仍然構成最小生成樹的子集，則稱這條邊為安全邊
求MST的一般演算法可描述為：針對圖G，從空樹T開始，往集合T中逐條選擇并加入n-1條安全邊（u，v），最終生成一棵含n-1條邊的MST，
當一條邊（u，v）加入T時，必須保證T∪{(u，v)}仍是MST的子集，我們將這樣的邊稱為T的安全邊，
GENERIC-MST(G,w)
A <- ?
while A does not form a spanning tree
do find an edge(u,v) that is safe for A
A <- A ∪ {(u,v)}
return A
- 如何判斷邊是否安全？
- 例：u∈S，v∈V-S，則（u，v)是否安全？
- 例：u，v∈S，則（u，v)是否安全？
- 解答：集合S，集合V-S同屬于集合V，則S與V-S兩集合間的最短距離，假設兩集合間存在這條邊（u，v)，則必然有u∈S，v∈V-S，如果邊（u，v)的權值是跨越割集的所有邊中最小的，我們就稱這條邊是當前來講可選的最輕的一條邊，而且是一條安全邊，能夠跨域割集的邊是安全邊，能夠構成子集的一定是所有跨越中最小的
? Kruskal's Algorithm是從邊出發，尋找（安全）邊；Prim's Algorithm是從點出發，尋找（安全)邊
如圖，{a,b,d,e}∈S，{c,i,h,g,f}∈V-S， 則（c,d)是一條安全邊
Kruskal's Algorithm
初始A是一個森林，每一個加入A的安全邊應該總是權值最小的連接兩個不同點的邊，
-
初始化每個頂點都是單獨一棵樹，即有n個集合，每個集合有一個元素，A<-?
-
在森林中任意兩棵樹之間找一棵權值最小的安全邊(u,v) //需對所有邊的權值進行排序
-
將（u，v)加入到A并合并這兩棵樹變成一棵樹，
-
Repeat step 2 and 3 until A forms a spanning tree.(直到找到n-1條邊)
Prim's Algorithm
初始A是一棵樹，每次加入到A的安全邊總是連接A和A之外某個結點的權值最小的邊，
- 從任意一個結點r出發，把r加到頂點集合U中，U初始為空集
- 找到最小權值邊（u，v)，u∈U，v∈V-U，把邊（u，v)加入到A，把v加入到U
- Repeat 2 until A forms a spanning tree or U = V.
問題
- key[u] 保存的是連接點u和樹中結點的所有邊中最小邊的權重
- Π[u] u的父節點
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536040.html
標籤：其他
上一篇：Codeforces 1646 D. Weight the Tree
下一篇：Tomcat多實體部署