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

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

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

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

4、ize 30 #define 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); printf(请输入该图的顶点信息:n); for(

5、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(请输入第%d条边的顶点序号：,k); scanf(%c %c,&ch1,&ch2);printf(请输入第%d条边的权值大小：,k); scanf(%d,&ch3); for(i=1;ch1!=G.vexsi;i+); for(j=1;ch2!=G.vexsj;j+)

6、;ep.vexh=i;ep.vext=j; ep.weight=G.edgesij.w=ch3; /权值 ep.flag=0;p+; return G;流程如图4.1所示创建图使用的是函数MGraph CreateMGraph()，该图的存储结构是邻接矩阵，先对图的结构体进行定义，再进行初始化。在函数中需要手动输入图的参数（如顶点数、边数、顶点信息、相连接的顶点、边的权值等）用来建立图并且确定图的邻接矩阵。最后在完成图的信息输入即建立图以后输出图的邻接矩阵表。模块二：求图的最小生成树。void minitree_KRUSKAL(MGraph *G) int i,min,j,k;VEX tM;

7、for(i=1;in;i+)ti.data=G-vexsi;ti.jihe=i;i=1; while (in) min=MaxVertexNum; for (j=0;je;j+) if (ej.weightmin&ej.flag=0) min=ej.weight; k=j; if (tek.vexh.jihe!=tek.vext.jihe) ek.flag=1; for (j=1;jn;j+) if (tj.jihe=tek.vext.jihe) tj.jihe=tek.vexh.jihe; tek.vext.jihe=tek.vexh.jihe; i+; else ek.flag=2; pr

8、intf(克鲁斯卡尔最小生成树：n);for (i=0;ie;i+) if (ei.flag=1) printf(%d,%d) %dn,ei.vexh,ei.vext,ei.weight);/输出最小生成树该步骤应用的是克鲁斯卡尔算法，它的基本思想是：每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST（Minimum Spanning Tree最小生成树），并将所在的2个连通分量合并，直到只剩一个连通分量。 流程如图4.2所示。图4.1图4.25 程序编码#include #define MaxVertexNum 100 /最大顶点个数#define M 30typed

9、ef enumFALSE,TRUEBoolean;Boolean visitedMaxVertexNum; /访问标志数组typedef char VertexType;typedef int EdgeType;typedef struct Lnodeint w;/相应一条边的权值Link;typedef structVertexType vexsMaxVertexNum;/顶点表 Link edgesMaxVertexNumMaxVertexNum; /图中当前的相连接的两个顶点int n,e;/图中当前的顶点数和边数MGraph; typedef struct char data; int

10、 jihe; VEX; typedef struct int vexh,vext;/边顶点 int weight;/权值int flag;/标记EDGE; 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); scanf(%d,%d,&(G.n),&(G.e); printf(请输入

11、该图的顶点信息: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(请输入第%d条边的顶点序号：,k); scanf(%c %c,&ch1,&ch2);printf(请输入第%d条边的权值大小：,k); scanf(%d,&ch3); for(i=1;ch1!=G.vexsi;i+); for(j=1;

12、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;in;i+)ti.data=G-vexsi;ti.jihe=i;i=1; while (in) min=MaxVertexNum; for (j=0;je;j+) if (ej.weightmin&ej.flag=0) min=ej.weight; k=j;

13、if (tek.vexh.jihe!=tek.vext.jihe) ek.flag=1; for (j=1;jn;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;ie;i+) if (ei.flag=1) printf(%d,%d) %dn,ei.vexh,ei.vext,ei.weight);/输出最小生成树 /*主函数调用*/ int main() MGraph G;prin

14、tf(n);printf(*n); printf(* 克鲁斯卡尔算法求图的最小生成树 *n);printf(*n); G=CreateMGraph();/建立该图的邻接矩阵minitree_KRUSKAL(&G);/克鲁斯卡尔算法最小生成树 return 0; 6 程序调试与测试运行程序后如图所示 图6.1输入错误数组后如图所示 图6.2继续输入正确数组后如图所示 图6.37 结果分析程序运行时如果输入的点大于边减一再乘以边除以2，那就是说输入的数组是错误的，此时程序提醒输入错误，在重新输入。如果输入正确那么程序会输出最小生成树。8 总结这个程序运用函数CreateMGraph来实现图的创建，以及图的相关信息的存储。图的存储采用邻接矩阵存储结构。在运用函数minitree_KRUSKAL来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是本题所要求使用的。在整个程序中先调用函数CreateMGraph实现图的创