Spanning Tree - 演算法筆記

權重最小的生成樹。

可能有許多種。

Minimum Spanning Tree: Kruskal's Algorithm. 用途. 求出無向圖的 ... SpanningTree SpanningTree/SpanningForest 「生成樹」。

從一張圖取出一棵樹，包含圖上所有點。

可能有許多種。

當一張圖完全連通，則擁有生成樹。

當一張圖不連通，則沒有生成樹，而是擁有許多棵「生成子樹」構成的「生成森林」。

生成樹的權重，是樹上每條邊的權重總和。

MinimumSpanningTree 「最小生成樹」。

權重最小的生成樹。

可能有許多種。

MinimumSpanningTree:Kruskal'sAlgorithm 用途 求出無向圖的其中一棵最小（大）生成樹。

若是圖不連通，則是求出其中一叢最小（大）生成森林。

想法 一、一個單獨的點，視作一棵最小生成子樹MSS。

二、兩棵MSS連結成一棵MSS，以兩棵MSS之間權重最小的邊進行連結，顯然是最好的。

三、三棵MSS連結成一棵MSS，以其中兩棵MSS之間權重最小的邊進行連結，才連結第三棵，總是比較好。

點的視角：不斷連結兩棵MSS、合併兩棵MSS，得到最小生成樹（森林）。

邊的視角：依序以權重最小、次小、……的邊，嘗試連結各棵MSS，得到最小生成樹（森林）。

演算法 一、圖上每一個點，各自是一棵最小生成子樹MSS。

二、圖上所有邊，依照權重大小，由小到大排序。

三、嘗試圖上所有邊，作為最小生成樹（森林）的邊： 　甲、兩端點分別位於兩棵MSS，也就是產生了橋： 　　　用這條邊連結兩棵MSS，合併成一棵MSS。

　　　這條邊是最小生成樹（森林）上的邊。

　乙、兩端點皆位於同一棵MSS，也就是產生了環： 　　　捨棄這條邊。

尋找最小生成樹的過程： 尋找最大生成樹的過程： 時間複雜度 一、排序圖上所有邊。

O(ElogE)。

二、連結MSS，採用「Disjoint-setsForest」。

O(Eα(E,V))。

總時間複雜度O(ElogE)。

如果兩點之間有多條邊，預先以GraphTraversal掃描一次所有邊，保留權重最小的邊，仍可求得正確答案。

兩點之間只剩下一條邊，邊數至多C(V,2)=V(V-1)/2=O(V²)條。

時間複雜度O(ElogE)可以改寫成O(ElogV²)=O(2ElogV)=O(ElogV)。

constintV=100,E=1000; structEdge{inta,b,c;}e[E]; //edgelist booloperator 迴圈的部份也可以寫成這樣。

//窮舉圖上所有邊，嘗試作為最小生成樹（森林）。

for(i=0,j=0;i=0)a=n[a]; if(n[b]>=0)b=n[b]; if(a==b)edge[i--]=edge[--E]; } } returnw1+w2; } 演算法 窮舉樹根，再仿效Dijkstra'sAlgorithm，時間複雜度O(V³)。

有差異的地方，不影響時間複雜度： 一、縮環最多V-1次（兩點縮成一點）。

縮環得到的新點，最多V-1個。

總點數最多2V，仍是O(V)。

二、縮環，採用Disjoint-setsForest。

O(Eα(E,V))。

如同Dijkstra'sAlgorithm，使用PriorityQueue可以得到更低的時間複雜度。

UVa11183