欢迎来到天天文库
浏览记录
ID:38551391
大小:20.33 KB
页数:13页
时间:2019-06-14
《最小生成树克里斯卡尔(kruskal)c程序(Minimum spanning tree Chris Carle (Kruskal) C program)》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、最小生成树克里斯卡尔(kruskal)c程序(MinimumspanningtreeChrisCarle(Kruskal)Cprogram)#包括#定义N6#定义maxnum10000/**/定义一个最大整数定义邻接矩阵类型/**/typedefint邻接钜阵[n+1][n+1];0号单元没用/**/typedefstruct{国际fromvex,托维克斯;体重;}边缘;typedef边缘*EdgeNode;国际arcnum;/**/边的个数建立图的邻接矩阵/**/虚空CreatMatrix(邻
2、接钜阵Ga){int,j,k,e;printf(“图中有%d个顶点n,n);对于(i=1;;i=n;i++){对于(j=1;j=n;j++){如果(i=j){GA[我][J]=0;/*对角线的值置为0*/}别的{GA[我][J]=maxnum;/**/其它位置的值初始化为一个最大整数}}}printf(“请输入边的个数:”);scanf(“%d”,与arcnum);printf(“请输入边的信息,按照起点,终点,权值的形式输入:”);为(k=1;K<=arcnum;K+){scanf(“%d,%d,%d”,和
3、我,和J,E);/**/读入边的信息如果(i=j){e=0;arcnum--;}遗传算法[i];遗传算法[J];}}初始化图的边集数组/**/无效的InitEdge(边缘GE,intm){inti;对于(i=1;i=m;i++){通用I,重量=0;}}根据图的邻接矩阵生成他的边集数组/**/无效getedgeset(邻接钜阵Ga,边缘GE){int,j,k=1;对于(i=1;;i=n;i++){对于(j=i+1;j=n;j++){如果(i[j]]!=0和GA[i]!=maxnum){GE[K]。fromvex=我
4、;GE[K]。托维克斯=J;[重量];钾+;}}}}按升序排列图的边集数组/**/无效的SortEdge(边缘GE,intm){int,j,k;边缘温度;对于(i=1;i重量>重量]{k=j;}}如果(k)!=i){温度=GE[我];锗[锗];通用电气;}}}输出边集数组的每条边/**/无效的外边界条件(边缘GE,inte){inti;printf(“按照起点,终点,权值的形式输出的最小生成树为:”);对于(i=1;i=e;i++){p
5、rintf(“%d,%d%d”,葛[我]。fromvex,GE[我]。托维克斯,GE[我]。重量);}}初始化表示最小生成树的两点之间是否有路径的邻接矩阵/**/无效routegainit(邻接钜阵routega){int,j;对于(i=1;;i=n;i++){对于(j=1;j=n;j++){如果(i=j){routega[我][J]=1;/*表示最小生成树的两点之间是否有路径的邻接矩阵元素为1表示两点间有路径*/}别的{routega[我][J]=0;/*表示最小生成树的两点之间是否有路径的邻接矩阵元素为0
6、表示两点间没有路径*/}}}}/*以顶点M为起点深度遍历最小生成树子图*若顶点我在深度遍历序列中,则表示顶点我与顶点M之间有路径,同时把连通顶点表中以我为下标的元素置为1*/虚空DfsMinTree(邻接钜阵routega,intm,intvextable[]){IntJ;vextable[M]=1;对于(j=1;j=n;j++){如果(m)!=J&routega[J][M]==1和vextable[J]==0){DfsMinTree(routega,J,vextable);}}}**/whethertomodi
7、fytherepresentationoftheadjacencymatrixpathbetweentwopointsoftheminimumspanningtreeVoidchangerouteGA(adjmatrix,routeGA,int,m){Int,I,j;Intvextable[n+1];/*thearrayiscalledtheconnectedvertextablesubscriptrepresentthecorrespondingvertex,ifthearrayelements1saidtha
8、tthepathbetweenthecorrespondingvertexelementsubscript*orvertexm2andvertexM1For(i=1;i<=n;i++){/**/initializeconnectedvertextableVextable[i]=0;}DfsMinTree(routeGA,m,vextable);For(i=1;i<=(n-
此文档下载收益归作者所有