http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3204一道很直接的最小生成樹，題中給出了權值矩陣，本應給用Prim的，但是為了練習一下并查集的使用，選擇了Kruskal。
前面我寫過Kruskal，但是集合的表示用的是線性表，每次合并都要花費O(N)的時間，效率較低。這次用了并查集——集合的樹形表示，能把合并集合的時間降到O(logN)。
定義setTree[]來表示每個節點所屬的集合，以及所屬集合的樹的深度。合并集合時選擇深度潛的那個作為樹根，樹的深度不變；如果兩棵樹的深度相同，合并后樹根的深度要加1。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 110
typedef struct
{
int b;
int e;
int len;
}Edge;
typedef struct
{
int p;
int d;//deep
}Set;
Edge usedEdges[LEN];
Edge edges[LEN * LEN];
int n;
Set setTree[LEN];
int parent(int i)
{
while(setTree[i].p != i)
{
i = setTree[i].p;
}
return i;
}
int Min(int a, int b)
{
if(a < b)
return a;
else
return b;
}
int Max(int a, int b)
{
if(a > b)
return a;
else
return b;
}
int Kruskal(int k)
{
int i, j, t;;
for(i = 0; i < n; i++)
{
setTree[i].p = i;
setTree[i].d = 0;
}
t = 0;
for(i = 0; i < k; i++)
{
int b = edges[i].b;
int e = edges[i].e;
int setb = parent(b);
int sete = parent(e);
if(setb != sete)
{
usedEdges[t].b = Min(b, e);
usedEdges[t].e = Max(b, e);
usedEdges[t].len = edges[i].len;
t++;
if(setTree[setb].d > setTree[sete].d)
{
setTree[sete].p = setb;
}
else if(setTree[setb].d < setTree[sete].d)
{
setTree[setb].p = sete;
}
else
{
setTree[setb].p = sete;
setTree[sete].d++;
}
}
}
return t;
}
int cmp(const void *a, const void *b)
{
Edge *a0 = (Edge*)a;
Edge *b0 = (Edge*)b;
return a0 -> len - b0 -> len;
}
int cmp1(const void *a, const void *b)
{
Edge *a0 = (Edge*)a;
Edge *b0 = (Edge*)b;
if(a0 -> b != b0 -> b)
return a0 -> b - b0 -> b;
else
return a0 -> e - b0 -> e;
}
int main()
{
int i, j, k;
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
k = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
int a;
scanf("%d", &a);
if(a != 0)
{
edges[k].b = i;
edges[k].e = j;
edges[k].len = a;
k++;
}
}
qsort(edges, k, sizeof(Edge), cmp);
int t = Kruskal(k);
qsort(usedEdges, t, sizeof(Edge), cmp1);
if(t == n - 1)
{
for(i = 0; i < n - 1; i++)
{
if(i == 0)
printf("%d %d", usedEdges[i].b + 1, usedEdges[i].e + 1);
else
printf(" %d %d", usedEdges[i].b + 1, usedEdges[i].e + 1);
}
}
else
printf("-1");
printf("\n");
}
}
posted on 2012-04-26 10:01
小鼠標 閱讀(328)
評論(0) 編輯 收藏 引用 所屬分類:
圖論