kruskal.txt

学数据结构的同学可以看看

/*克鲁斯卡尔算法构造最小生成树*/ 
#define MAXEDGE 30 /*MAXEDGE为最大的边数*/ 
struct edges /*边集类型,存储一条边的起始顶点bv、终止顶点tv和权w*/ 
{ 
int bv,tv,w; 
}; 
typedef struct edges edgeset[MAXEDGE]; 
int seeks(int set[],int v) 
{ 
int i=v; 
while (set[i]>0) i=set[i]; 
return(i); 
} 
kruskal(edgeset ge,int n,int e) 
/*ge表示的图是按权值从小到大排列的*/ 
{ 
int set[MAXEDGE],v1,v2,i,j; 
for (i=1;i<=n;i++) set[i]=0; /*给set中的每个元素赋初值*/ 
i=1; /*i表示待获取的生成树中的边数,初值为1*/ 
j=1; /*j表示ge中的下标,初值为1*/ 
while (j<n && i<=e) /*按边权递增顺序,逐边检查该边是否应加入到生成树中*/ 
{ 
v1=seeks(set,ge[i].bv); /*确定顶点v所在的连通集*/ 
v2=seeks(set,ge[i].tv); 
if (v1!=v2) /*当v1,v2不在同一顶点集合,确定该边应当选入生成树*/ 
{ 
printf("(%d,%d) ",ge[i].bv,ge[i].tv); 
set[v1]=v2; 
j++; 
} 
i++; 
} 
} 
main() 
{ 
int n=7,e=10; 
edgeset mx; 
mx[1].bv=4;mx[1].tv=6;mx[1].w=30; 
mx[2].bv=2;mx[2].tv=5;mx[2].w=40; 
mx[3].bv=4;mx[3].tv=7;mx[3].w=42; 
mx[4].bv=3;mx[4].tv=7;mx[4].w=45; 
mx[5].bv=1;mx[5].tv=2;mx[5].w=50; 
mx[6].bv=4;mx[6].tv=5;mx[6].w=50; 
mx[7].bv=3;mx[7].tv=4;mx[7].w=52; 
mx[8].bv=1;mx[8].tv=3;mx[8].w=60; 
mx[9].bv=2;mx[9].tv=4;mx[9].w=65; 
mx[10].bv=5;mx[10].tv=6;mx[10].w=70; 
printf("最小生成树边集:\n "); 
kruskal(mx,n,e); 
}