最小生成樹，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
小鼠標 閱讀(484)
評論(0) 編輯 收藏 引用 所屬分類:
圖論