//Kruskal(克鲁斯卡尔)算法 //杨鑫 #include <stdio.h> #include <stdlib.h> #define MAX 1000 #define MAXE MAX #define MAXV MAX typedef struct { int beginvex1; //边的起始顶点 int endvex2; //边的终止顶点 int weight; //边的权值 }Edge; void kruskal(Edge E[],int n,int e) { int i,j,m1,m2,sn1,sn2,k; int vset[MAXV]; for(i=1;i<=n;i++) //初始化辅助数组 { vset[i]=i; } k=1; //表示当前构造最小生成树的第k条边,初值为1 j=0; //E中边的下标,初值为0 while(k < e) //判断是否加入了最小生成树中 { m1=E[j].beginvex1; m2=E[j].endvex2; //取一条边的两个邻接点 sn1=vset[m1]; sn2=vset[m2]; //分别得到两个顶点所属的集合编号 if(sn1 != sn2) //判断是否有回路 { printf("(v%d,v%d): %d\n",m1,m2,E[j].weight); k++; //生成边数增l if(k>=6) break; for(i=1;i<=n;i++) //两个集合统一编号 { if (vset[i]==sn2) //集合编号为sn2的改为sn1 vset[i]=sn1; } } j++; //扫描下一条边 } } int main() { Edge E[MAXE]; int nume,numn; //这里我写死,下面可以自己输入 //printf("输入边数和顶数:\n"); //scanf("%d%d",&nume,&numn); nume=10; numn=6; /* printf("请输入各边及对应的的权值(起始顶点 终止顶点 权值)\n"); for(int i=0;i<nume;i++) scanf("%d%d%d",E[i].beginvex1,E[i].endvex2,E[i].weight); */ //在这里对输入的数据进行排序,达到假设的要求,即:假设数组E存放图G中的 //所有边,且边已按权值从小到大的顺序排列 E[9].beginvex1=1; E[9].endvex2=2; E[9].weight=6; E[0].beginvex1=1; E[0].endvex2=3; E[0].weight=1; E[4].beginvex1=1; E[4].endvex2=4; E[4].weight=5; E[6].beginvex1=2; E[6].endvex2=3; E[6].weight=5; E[2].beginvex1=2; E[2].endvex2=5; E[2].weight=3; E[8].beginvex1=1; E[8].endvex2=2; E[8].weight=6; E[5].beginvex1=3; E[5].endvex2=4; E[5].weight=5; E[7].beginvex1=3; E[7].endvex2=5; E[7].weight=6; E[3].beginvex1=3; E[3].endvex2=6; E[3].weight=4; E[1].beginvex1=4; E[1].endvex2=6; E[1].weight=2; kruskal(E,numn,nume); return 0; }
结果: