最小生成树示例程序_Kruscal算法
May 1, 2013
Graph
输入:顶点个数n和边数m,然后输入m行,每行输入格式:u v w 分别表示两个顶点和这个边的权值,顶点序号从1开始 输出:一次选择的各条边和最终的最小生成树的权值
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MAXN 1000
#define MAXM 1000
int parent[MAXN], n, m;
typedef struct Edge {
int u, v, w;
bool operator < (const Edge &other) const {
return w < other.w;
}
}Edge;
Edge edge[MAXM];
void init() {
for (int i = 1; i <= n; ++i) parent[i] = -1;
}
int Find(int x) {
int s = x, tmp;
while (parent[s] >= 0) s = parent[s];
while (s != x) {
tmp = parent[x]; parent[x] = s; x = tmp;
}
return s;
}
void Union(int a, int b) {
int x = Find(a), y = Find(b), tmp = parent[x] + parent[y];
if (parent[x] < parent[y]) {
parent[y] = x; parent[x] = tmp;
} else {
parent[x] = y; parent[y] = tmp;
}
}
void kruscal() {
int cnt = 0, sum = 0, i, u, v, w;
for (i = 0; i < m; ++i) {
u = edge[i].u; v = edge[i].v; w = edge[i].w;
if (Find(u) != Find(v)) {
cnt++; sum += w; printf("%d %d %d\n", u, v, w); Union(u, v);
}
if (cnt == n - 1) break;
}
printf("%d\n", sum);
}
int main(void) {
freopen("kruscal.in", "r", stdin);
while (~scanf("%d%d", &n, &m)) {
int i, u, v, w;
for (i = 0; i < m; ++i) {
scanf("%d%d%d", &u, &v, &w); edge[i].u = u; edge[i].v = v; edge[i].w = w;
}
init(); sort(edge, edge+m); kruscal();
}
return 0;
}
呵呵