#define N 255 typedef struct {int begin,end; int weight; }graphedge;
int getedge(graphedge edge[]); void swap(int * p1,int * p2);
void sortedge(graphedge edge[],int k); int find(int father[],int e);
void kruskal(graphedge edge[],int k); int main(void) {
int n; /*n为图的实际边树*/ graphedge edgea[N]; /*存储图的数组*/
n=getedge(edgea); /*将图的顶点、边和权输入数组*/
sortedge(edgea,n); /*将图的边集数组按边权值排序*/
kruskal(edgea,n); /*求带权的最小生成树*/ return 0; }
int getedge(graphedge edge[]) /*建立图的数组，并返回图的边数*/
{
int k,a,b; int c;
printf(\"请输入图的总边树：\\n\"); scanf(\"%d\ for(int i=1;i<=k;i++) { printf(\"起点 终点 权 =\"); scanf(\"%d %d %d\ edge[i].begin=a; edge[i].end=b; edge[i].weight=c;
} return (k); }
void swap(int* p1,int* p2) /*交换函数*/ {
int temp; temp=*p1; *p1=*p2; *p2=temp; }
void sortedge(graphedge edge[],int k) /*将所有的边按权值排序*/
{
for(int i=1;ifor(int j=i+1;j<=k;j++) {if(edge[i].weight>edge[j].weight)
swap(&edge[i].begin,&edge[j].begin); }
int find(int father[],int e) /*查找与起点连接的终点数组*/
{
}
swap(&edge[i].end,&edge[j].end); swap(&edge[i].weight,&edge[j].weight);
int f=e;
while(father[f]>0)
f=father[f];
return (f); }
void kruskal(graphedge edge[],int k) /*构造最小生成树的Kruskal算法*/
{
int father[N],begin1,end1,i; printf(\"最小生成树为：\\n\"); for(i=1;i<=k;i++)
father[i]=0;
for(i=1;i<=k;i++) {
printf(\"%d\%d\%d\\n\
}
begin1=find(father,edge[i].begin); end1=find(father,edge[i].end); if(begin1!=end1) {
father[begin1]=end1;
} }
二、 运行结果：