最小生成树，Kruskal算法。
算法很简单，先把边排序，依次找链接不同集合的最小边，合并集合，当只有一个集合的时候结束。问题在于如何实现集合合并，学长们说合并时用并查集效率较高。我这里用不同的数字代表不同的集合，每次合并都要遍历所有集合，改变集合数字，时间复杂度O(n)。
Ege结构体中刚开始把b、d两个变量定义成了char，数据小的时候没问题，当数据大于127时就会爆掉，纠结了很久。
qsort()函数用法：void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));
base是数组起始下标；
nelem是元素个数；
width是单个元素的大小；
fcmp是比较函数。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LEN 600000
typedef struct
{
int x;
int y;
int bl;//set the point belong to
}Point;
typedef struct
{
int b;//begin point//最纠结的就是这里，刚开始把它定义成了char，爆了很久啊。
int d;//end point
int len;
}Ege;
Point p[760];
Ege eg[LEN];
int cmp(const void *a, const void *b)
{
Ege * a0 = (Ege*)a;
Ege * b0 = (Ege*)b;
return a0 -> len - b0 -> len;
}
int k;
void MakeEge(int n)
{
int i, j;
k = 0;
for(i = 0; i < n - 1; i++)
for(j = i + 1; j < n; j++)
{
eg[k].b = i;
eg[k].d = j;
eg[k].len = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
k++;
}
}
int main()
{
int N, M;
int i, j;
int en;
int min, max;
FILE *fp = fopen("outege.txt", "w");
while(scanf("%d", &N) == 1)
{
en = 0;
for(i = 0; i < N; i++)// read point
{
scanf("%d%d", &p[i].x, &p[i].y);
p[i].bl = i;
}
scanf("%d", &M);
for(i = 0; i < M; i++)//read M eges
{
int b, d, b0, d0;
scanf("%d%d", &b0, &d0);
b = b0 - 1;
d = d0 - 1;
if(p[b].bl != p[d].bl)
{
en++;
min = p[b].bl < p[d].bl ? p[b].bl : p[d].bl;
max = p[b].bl > p[d].bl ? p[b].bl : p[d].bl;
for(j = 0; j < N; j++)// connect set
{
if(p[j].bl == max)
{
p[j].bl = min;
}
}
}
}
MakeEge(N);
qsort(eg, N * (N - 1) / 2, sizeof(Ege), cmp);
for(i = 0; en < N - 1 && i < N * (N - 1) / 2; i++)//test each eges
{
int b, d;
b = eg[i].b;
d = eg[i].d;
if(p[b].bl != p[d].bl)
{
en++;
printf("%d %d\n", b + 1, d + 1);//out this ege
min = p[b].bl < p[d].bl ? p[b].bl : p[d].bl;
max = p[b].bl > p[d].bl ? p[b].bl : p[d].bl;
for(j = 0; j < N; j++)//connect set
{
if(p[j].bl == max)
{
p[j].bl = min;
}
}
}
}
}
return 0;
}
posted on 2012-04-19 17:28
小鼠标 阅读(457)
评论(0) 编辑 收藏 引用 所属分类:
图论