最小生成樹的Prim和Kruskal算法

一、Prim算法

1.算法原理：

和Dijkstra算法非常相似，都是從某個頂點開始，通過将邊添加到新的集合中去。此算法添加邊的原則描述如下：

設新的節點集合為V，由新的節點集合确定的邊集為E = { (i, j) | i, j ∈V } （當然這些邊構成的圖是一棵樹），每次将與V集合相連的點的不在E集合的最小邊添加到E中去，同時将相連的點添加到V中去，在這個過程中，從原來的圖中删除點和邊。在添加的過程中還要注意不能有環的産生

2.難點：

這個算法主要的難點在于如何高效的确定我們需要添加的邊，如果每次都周遊V集合的所有相關邊，那麼算法的複雜度比較高，O(n^2)；但是我們可以借鑒在Dijkstra中的處理方法，通過隊列來管理我們需要使用的邊。優化以後算法複雜度變為O(elogv)

int cost[maxn][maxn];	//表示邊權值
int mincost[maxn];	//從集合V出發的邊每個頂點的最小權值
bool used[maxn];	//表示頂點i是否被取出，包含在V中
int vertex_num;	//頂點數

int Prim() {
	//未加入的點的邊權值為INF
	fill(mincost, mincost + vertex_num, INF);
	fill(used, used + vertex_num, false);

	mincost[0] = 0;
	int res = 0;

	while (true) {
		int v = -1;

		for (int u = 0; u < vertex_num; u++) {
			if (!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
		}

		if (v == -1) break;
		used[v] = true;
		res += mincost[v];

		for (int u = 0; u < vertex_num; u++) {
			if (!used[u]) mincost[u] = min(mincost[u], cost[v][u]);
		}
	}
	return res;
}
           

關于如下語句的解釋為：對于沒有加入V的點，如果該點與已經在V中的點有連接配接，那麼使用邊權值進行最小值的更新（已經在V中的點就沒有必要更新了，因為更新也沒有意義）

if (!used[u]) mincost[u] = min(mincost[u], cost[v][u]);
           

Prim算法的隊列維護方式：

typedef pair<int, int> P;	//first: mincost, second: vertex
int cost[maxn][maxn];
bool used[maxn];
int vertex_num;

int Prime() {
	priority_queue<P, vector<P>, greater<P> > que;
	que.push(P(0, 0));
	int v = -1, ans;
	while (true) {
		if (!que.empty()) {
			v = que.top().second;
			ans += que.top().first;
			que.pop();
		}

		if (v == -1) break;
		used[v] = true;

		for (int u = 0; u < vertex_num; u++) {
			if (!used[u]) que.push(P(cost[v][u], u));
		}
	}
	return ans;
}
           

二、Kruskal算法

1.算法原理：

Kruskal算法按照邊的權值順序從小到大檢視一遍，如果沒有圈産生，就把目前邊加入到生成樹中

2.算法實作難點：

主要是判斷是否産生圈，在prim算法中，我們是對節點數進行考慮，有一個關于節點狀态的數組used［maxn］為我們排除那些已經被選取的點，然而這裡隻用到邊，是以沒有直接快速的方法去确定，但是我們可以利用并查集來排除産生環的情況，算法複雜度為O(elogv)

struct Edge {
	int u, v, cost;
};

int vertex_num, edge_num;	//頂點數，邊數
int pre_V[maxn_V];	//記錄頂點并查集
int rank[maxn_V];	//記錄階數
Edge edge[maxn_E];	//記錄邊

bool comp(const Edge& lhs, const Edge& rhs) {
	return lhs.cost < rhs.cost;
}

void init_union_find(int n) {
	for (int i = 0; i < vertex_num; i++) pre_V[i] = i;
}

int find(int value) {
	if (pre_V[value] == value) return value;
	return pre_V[value] = find(pre_V[value]);
}

void unite(int lhs, int rhs) {
	lhs = find(lhs);
	rhs = find(rhs);
	if (lhs == rhs) return ;
	if (rank[lhs] < rank[rhs]) {
		pre_V[lhs] = rhs;
	}
	else {
		pre_V[rhs] = lhs;
		if (rank[rhs] == rank[lhs]) rank[lhs]++;
	}
}

bool same(int lhs, int rhs) {
	return find(lhs) == find(rhs);
}

int Kruskal() {
	sort(edge, edge + edge_num, comp);
	init_union_find(vertex_num);
	int ans = 0;
	for (int i = 0; i < edge_num; i++) {
		Edge e = edge[i];
		if (!same(e.u, e.v)) {
			unite(e.u, e.v);
			ans += e.cost;
		}
	}
	return ans;
}