-
算法说明
克鲁斯卡尔算法,利用边贪心,先对边排序,每次加入最小的边,使用并查集,判断边的端点是否已经在同一个集合中即确定要不要加入这条边
- 源代码
#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算法