离散大作业.doc

离散数学导论大作业---------最小生成树一问题描述:求下图的最小生成树11**********abcdef二,:Kruskal算法每次选择n-1条边,所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分e步,其中e是网络中边的数目。按耗费递增的顺序来考虑这e条边,每次考虑一条边。当考虑某条边时,若将其加入到已选边的集合中会出现环路,则将其抛弃,否则,将它选入。:#include<>#include<>#include<>#definename5//。。。。。。。。。。。。。。。。。。。。。。。。。。顶点名占5个字符#definevertexnum40//。。。。。。。。。。。。。。。。。。。顶点数目最多为40typedefcharVertex[name];//。。。。。。。。。。。。。。。顶点名字串typedefintAdjMatrix[vertexnum][vertexnum];//邻接距阵structMGraph//。。。。。。。。。。。。。。。。。。。。。。。。。。定义图的结构体类型{ Vertexvexs[vertexnum]; AdjMatrixarcs; intvexnum,um;};typedefstruct{ Vertexadjvex;//。。。。。。。。。。。。。。。。。。。。。。。。当前点 intlowcost;//。。。。。。。。。。。。。。。。。。。。。。。。。。代价}minside[vertexnum];//声明函数原型intLocateVex(MGraphG,Vertexu);voidCreateGraph(MGraph&G);intminimum(minsideSZ,MGraphG);voidMiniSpanTree_PRIM(MGraphG,Vertexu);//主函数intmain(){ MGraphg; CreateGraph(g); MiniSpanTree_PRIM(g,[0]); system("PAUSE"); return0;}intLocateVex(MGraphG,Vertexu)//。。。。。。。。。。。结点的定位{ inti; for(i=0;i<;++i)if(strcmp(u,[i])==0)returni; return-1;}voidCreateGraph(MGraph&G)//。。。。。。。。。。。。。。。。。。建立无向图{ inti,j,k,w; Vertexva,vb; printf("请输入无向图G的顶点数和边数(以空格为分隔)\n"); scanf("%d%d",&,&); printf("请输入%d个顶点的值(<%d个符):\n",,name); for(i=0;i<;++i)//。。。。。。。。。。。。。。。构造图的顶点集合 scanf("%s",[i]); for(i=0;i<;++i)//。。。。。。。。