Algorithm - Minimum Spanning Tree

Course

可以參考我做的課程簡報：

MST & Shortest Path

Minimum Spanning Tree 最小生成樹

最小生成樹
求出無向圖的其中一棵最小生成樹
若是圖不連通，則是求出其中一叢最小生成森林

Kruskal’s Algorithm

生成步驟

將圖上所有邊依照權重大小由小到大排序
依序比較每條邊

1. 若此邊上的兩端點已處於同棵樹，則捨棄此邊
2. 若此邊上的兩端點未處於同棵樹，則利用此邊連結兩棵生成森林

Disjoint Set

關於 Disjoint Set 的基本觀念可以參考我的這篇文章：

Algorithm - Disjoint Set

int find(int x){
	if(parent[x] < 0) return x;
	return parent[x] = find(parent[x]);
}

void Union(int a, int b){
	a = find(a);
	b = find(b);

	if(a != b){
		if(parent[a] < parent[b]){
			parent[a] += parent[b];
			parent[b] = a;
		}
		else{
			parent[b] += parent[a];
			parent[a] = b;
		}
	}
}

void kruskal(){
    // 先讓所有人父節點都是 -1 (沒有父親)
    memset(parent, -1, sizeof(parent));
    sort(edge.begin(), edge.end());

    int i, j;
    total = 0;
    // i < N-1 因為一顆樹最多只會有 N (點的數量) -1 條邊
    // j < M (M 是目前測資給予的邊的總數量 可能會有重邊 所以可能不只 N-1 條邊)
    for(i = 0, j = 0; i < N-1 && j < M; ++i){
        // 如果 u 和 v 的祖先相同 則 ++j (祖先相同會產生環 所以不要建立邊)
        while(find(edge[j].u) == find(edge[j].v)) ++j;

        // 若不會產生環 則讓兩點之間產生橋 (連接兩顆子生成樹)
        Union(edge[j].u, edge[j].v);
        total += edge[j].w;
        ++j;
    }
}

Prim’s Algorithm

生成步驟

選擇任意一點作為根

屢次找不在生成樹上
離生成樹最近的點
(找與生成樹相連最短的邊)

UVA Problem

UVA 00908 - Re-connecting Computer Sites