-
算法說明
克魯斯卡爾算法,利用邊貪心,先對邊排序,每次加入最小的邊,使用并查集,判斷邊的端點是否已經在同一個集合中即确定要不要加入這條邊
- 源代碼
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 1000 + 1
struct edge {
int u, v, cost;
node(int a, int b, int c) {
u = a;
v = b;
cost = c;
}
};
int n, m; //頂點和邊數
edge e[maxn]; //這麼多邊
int father[maxn];
int findFather(int x) { //并查集
if(father[x] == true) return x;
return father[x] = findFather(father[x]);
}
bool cmp(edge a, edge b) {
return a.cost < b.cost;
}
int kruskal(int u) { //從頂點u開始出發
fill(father, father + n, true); //初始化并查集
int sum = 0; //邊權和
int edgeNum = 0;
sort(e, e + m, cmp); //邊排序
for(int i = 0; i < m; i++) {
int faU = findFather(e[i].u);
int faV = findFather(e[i].v);
if(faU != faV) {
father[faU] = faV; //合并集合
sum += e[i].cost;
if(edgeNum++ == n - 1) break;
}
}
if(edgeNum != n - 1) return -1;
return sum;
}
int main() {
//input
freopen("kruskal'sAlgorithm.txt", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].cost);
}
int distance = kruskal(1); //可以從任意一點出發
printf("%d", distance);
return 0;
}
- 輸入資料
算法導論 · 貪心政策 · kruskal算法 - 運作結果
算法導論 · 貪心政策 · kruskal算法