C语言实现最小生成树之kruskal（克鲁斯卡尔）算法

//Kruskal(克鲁斯卡尔)算法//杨鑫#include <stdio.h>#include <stdlib.h>#define MAX 1000#define MAXE MAX#define MAXV MAXtypedef 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条边，初值为1j=0;//E中边的下标，初值为0while(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++;//生成边数增lif(k>=6)break;for(i=1;i<=n;i++) //两个集合统一编号{if (vset[i]==sn2) //集合编号为sn2的改为sn1vset[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;}

结果：

在人生的道路上，谁都会遇到困难和挫折，

相关文章：

你感兴趣的文章：

标签云：