1、 离散数学导论大作业-最小生成树一 问题描述：求下图的最小生成树1 113 9 87465102abcdef二，问题求解用Kruskal算法求解上述问题1. Kruskal的算法描述如下：K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。2. 代码如下：#
2、include#include#include#define name 5/。顶点名占5个字符#define vertexnum 40 /。顶点数目最多为 40typedef char Vertexname;/。顶点名字串typedef int AdjMatrixvertexnumvertexnum;/邻接距阵struct MGraph/。定义图的结构体类型Vertex vexsvertexnum;AdjMatrix arcs;int vexnum,arcnum;typedef structVertex adjvex;/。当前点int lowcost;/。代价minsidevertexnum;
3、/声明函数原型int LocateVex(MGraph G,Vertex u);void CreateGraph(MGraphint minimum(minside SZ,MGraph G);void MiniSpanTree_PRIM(MGraph G,Vertex u);/主函数int main()MGraph g;CreateGraph(g);MiniSpanTree_PRIM(g,g.vexs0);system(“PAUSE“);return 0;int LocateVex(MGraph G,Vertex u)/。 。 。 。 。 。 。 。 。 。 。结点的定位int i;for(i
4、=0;i0k=j;return k;void MiniSpanTree_PRIM(MGraph G,Vertex u)int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj;closedgek.lowcost=0;printf(“最小代价生成树的各条边为:n“);for(i=1;iG.vexnum;+i)k=minimum(closedge,G);printf(“(%s-%s)n“,closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for(j=0;jG.vexnum;+j)if(G.arcskjclosedgej.lowcost)strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj;3. 运行结果如下所示：
