数据结构,最小生成树克鲁斯卡尔算法的实现

1、摘要设计了一个用 C/C+ 编写程序实现克鲁斯卡尔最小生成树算vc+。法，该程序操作简单，界面清晰，易于为用户所接受关键词 ： 克鲁斯卡尔，邻接矩阵，最小生成树，1 课题描述 12 问题分析和任务定义 23 逻辑设计 34 详细设计 45 程序编码 116 程序调试与测试 177 结果分析 198 总结 20参考文献 211 课题描述用 C/C+ 编写程序实现克鲁斯卡尔最小生成树算法。 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要 n-1 条线路。 这是我们设计一个最小生成树的程序用来算出最节省经费的前提下 建立这个通信站。72 问题分析和任务定义假设连通网 N=( V,E

2、 ),则令最小生成树的初始状态为只有 n 个顶点而无边的非连通图 T=(V,) ，图中每个顶点自成一个连通分 量。在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的 连通分量上，则将此边加入到 T 中，否则舍去此边而选择下一条代 价最小的边。依次类推，直到 T 中所有顶点都在同一连通分量上为 止。3逻辑设计设计思想：采用邻接矩阵来存储图，然后采用克鲁斯卡尔算法 求出最小生成树。1) .定义结构体2) .采用邻接矩阵做存储结构创建图(函数模块一)。3) .采用克鲁斯卡尔算法求出该图的最小生成树(函数模块二)4) .在主函数里面分别调用以上各个函数，最终实现设计目的。4 详细设计4.1

3、 程序结构函数 CreateMGraph用来实现图的创建，以及图的相关信息的存储。图的存储采用 邻接矩阵存储结构。函数 minitree_KRUSKAL用来求图的最小生成树。图的最小生成树有普利姆算法和克鲁 斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是 本题所要求使用的。各个函数间的联系先调用函数 CreateMGraph 实现图的创建，然后调用函数 min itree_KRUSKAL求出该图的最小生成树4.2 设计说明在开始的时候添加一些限制条件方便函数的功能实现例如：#define MaxVertexNum 100 / 最大顶点个数#define QueueSize 30#d

4、efine M 30模块一：图的创建结构体定义为：typedef structVertexType vexsMaxVertexNum;/ 顶点表Link edgesMaxVertexNumMaxVertexNum; / 图中当前的 相连接的两个顶点int n,e;/ 图中当前的顶点数和边数MGraph;函数定义为：MGraph CreateMGraph()MGraph G;int i,j,k,ch3;char ch1,ch2;printf("请输入该图的顶点数和边数 :n");scanf("%d,%d",&(G.n),&(G.e);pri

5、ntf("请输入该图的顶点信息 :n");for(i=1;i<=G.n;i+)getchar();scanf("%c",&(G.vexsi);for(i=1;i<=G.n;i+)for(j=1;j<=G.n;j+)G.edgesij.w=0;printf(" 请 输 入 该 图 每 条 边 对 应 的 两 个 顶 点 的 名 称:n");for(k=1;k<=G.e;k+)scanf("%c",&ch1);printf(”请输入第c条边的顶点序号：",k);scan

6、f("%c %c",&ch1,&ch2);printf("请输入第d条边的权值大小：",k);scanf("%d",&ch3);for(i=1;ch1!=G.vexsi;i+);for(j=1;ch2!=G.vexsj;j+);ep.vexh=i;ep.vext=j;ep.weight=G.edgesij.w=ch3; /权值ep.flag=0;p+; return G;流程如图 4.1 所示创建图使用的是函数 MGraph CreateMGraph() ，该图的存储结 构是邻接矩阵，先对图的结构体进行定义，再

7、进行初始化。在函数 中需要手动输入图的参数(如顶点数、边数、顶点信息、相连接的 顶点、边的权值等)用来建立图并且确定图的邻接矩阵。最后在完 成图的信息输入即建立图以后输出图的邻接矩阵表。模块二：求图的最小生成树。void minitree_KRUSKAL(MGraph *G)int i,min,j,k;VEX tM;for(i=1;i<=G->n;i+)ti.data=G->vexsi;ti.jihe=i;i=1;while (i<G->n)min=MaxVertexNum;for (j=0;j<G->e;j+)if (ej.weight<min

8、&&ej.flag=0)min=ej.weight;k=j;if (tek.vexh.jihe!=tek.vext.jihe)ek.flag=1;for (j=1;j<=G->n;j+)if (tj.jihe=tek.vext.jihe)tj.jihe=tek.vexh.jihe;tek.vext.jihe=tek.vexh.jihe;i+; else ek.flag=2;printf(" 克鲁斯卡尔最小生成树： n");for (i=0;i<G->e;i+)if (ei.flag=1)printf("(%d,%d) %dn

9、",ei.vexh,ei.vext,ei.weight);/ 输 出最小生成树 该步骤应用的是克鲁斯卡尔算法，它的基本思想是：每次选不 属于同一连通分量 （保证不生成圈 ） 且边权值最小的顶点，将边加入 MST（MinimumSpanning Tree 最小生成树），并将所在的 2 个连通分 量合并，直到只剩一个连通分量。流程如图 4.2 所示j+9请输入第d条边的顶点 序号K+请输入第d条边的权值 大小i=1尸1return G4 .ch2!=G.vexsjep.vexh=i;e【p.vext=j;ep.weight=G.edgesij.w=ch3;/权值ep.flag=0;p+;

10、图4.1N 卜 ek.flag=2jv=G->ntjjihe=tek.vexh .jihe;tek.vext.jihe=te k.vexh.jihe; i+；ti.jihe=tek,vext.jihei=0i<G->eei.flag=1输出最小生成树图4.2115 程序编码#include <stdio.h>#define MaxVertexNum 100 / 最大顶点个数#define M 30typedef enumFALSE,TRUEBoolean;Boolean visitedMaxVertexNum; / 访问标志数组typedef char Verte

11、xType;typedef int EdgeType;typedef struct Lnodeint w;/ 相应一条边的权值Link;typedef structVertexType vexsMaxVertexNum; / 顶点表Link edgesMaxVertexNumMaxVertexNum; / 图中当前的相连 接的两个顶点int n,e; / 图中当前的顶点数和边数 MGraph;typedef structchar data;int jihe;VEX;typedef structint vexh,vext; / 边顶点int weight;/ 权值int flag;/ 标记EDG

12、E;EDGE eM; int p=0;/*图邻接矩阵的建*/MGraph CreateMGraph()MGraph G;int i,j,k,ch3;char ch1,ch2;printf(" 请输入该图的顶点数和边数 :n");scanf("%d,%d",&(G.n),&(G.e);while(G.e>(G.n-1)*G.n/2)printf(" 输入错误,请重新输入 :n");13scanf("%d,%d",&(G.n),&(G.e);printf(" 请输入该图的

13、顶点信息 :n"); for(i=1;i<=G.n;i+)getchar();scanf("%c",&(G.vexsi); for(i=1;i<=G.n;i+)for(j=1;j<=G.n;j+)G.edgesij.w=0;:n");printf(" 请输入该图每条边对应的两个顶点的名称 for(k=1;k<=G.e;k+)scanf("%c",&ch1);printf(”请输入第c条边的顶点序号：",k);scanf("%c %c",&ch1,&

14、amp;ch2);printf(”请输入第c条边的权值大小：",k);scanf("%d",&ch3);for(i=1;ch1!=G.vexsi;i+);for(j=1;ch2!=G.vexsj;j+);ep.vexh=i;ep.vext=j;ep.weight=G.edgesij.w=ch3; / 权值ep.flag=0;p+;return G;克鲁斯卡尔最小生成树/* */void minitree_KRUSKAL(MGraph *G) int i,min,j,k;VEX tM;for(i=1;i<=G->n;i+)ti.data=G-&g

15、t;vexsi;ti.jihe=i;i=1;while (i<G->n)min=MaxVertexNum;for (j=0;j<G->e;j+)if (ej.weight<min&&ej.flag=0)min=ej.weight;k=j;if (tek.vexh.jihe!=tek.vext.jihe)ek.flag=1;for (j=1;j<=G->n;j+)if (tj.jihe=tek.vext.jihe)tj.jihe=tek.vexh.jihe;tek.vext.jihe=tek.vexh.jihe;i+;else ek.fl

16、ag=2;printf(" 克鲁斯卡尔最小生成树： n");for (i=0;i<G->e;i+)if (ei.flag=1)15printf("(%d,%d) %dn",ei.vexh,ei.vext,ei.weight);/ 输出最小生成树/*主函数调用23printf(*n");printf("*克鲁斯卡尔算法求图的最小生成树*n");*int main()MGraph G;printf("n");H*printf(H*n");G=CreateMGraph(); / 建立该图的

17、邻接矩阵 minitree_KRUSKAL(&G); / 克鲁斯卡尔算法最小生成树return 0;6程序调试与测试运行程序后如图所示图6.1输入错误数组后如图所示图6.2继续输入正确数组后如图所示O £情2,输4,称 名 的 点顶 £ 3 4 4 个 11223314 B占J i m i 普鸟召召-V小 Tb点«處®-歳直点： 號权坝監監权 卫勺闵自勺肉!<勺也 ST5 -Prr .nJ- r*TT .nJ- r*TT lf*TT .nJ- 劈边边边边边边边一 fjj _r - r r - ? F -1S11V-23J44>-2 3入IAlAiAIAlAiAIAIA>-> > > 3蔦 I1 ; 4请请谊鼻喜请注覺Kll<2l<3Fr7 结果分析程序运行时如果输入的点大于边减一再乘以边除以 2，那就是说 输入的数组是错误的，此时程序提醒输入错误，在重新输入。如果 输入正确那么程序会输出最小生成树。8 总结这个程序运用函数 CreateMGraph 来实现图的创建， 以及图的相 关信息的存储。图的存储采用邻接矩阵存储结构。在运用函数 min itree_KRUSKAL来求图的最小生成树。图的最小生成树有普利姆 算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算