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

-摘 要设计了一个用C/C+编写程序实现克鲁斯卡尔最小生成树算法，该程序操作简单，界面清晰，易于为用户所承受。关键词：克鲁斯卡尔，邻接矩阵，最小生成树，vc+。. z.-. z.-目 录1 课题描述12 问题分析和任务定义23 逻辑设计34 详细设计45 程序编码106 程序调试与测试167 结果分析188 总结19参考文献20. z.-1课题描述用C/C+编写程序实现克鲁斯卡尔最小生成树算法。假设要在n个城市之间建立通讯联络网，那么连通n个城市只需要n-1条线路。这是我们设计一个最小生成树的程序用来算出最节省经费的前提下建立这个通信站。. z.-2问题分析和任务定义假设连通网N=V,E,那么令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,)，图中每个顶点自成一个连通分量。在E中选择代价最小的边，假设该边依附的顶点落在T中不同的连通分量上，那么将此边参加到T中，否那么舍去此边而选择下一条代价最小的边。依次类推，直到T中所有顶点都在同一连通分量上为止。. z.-3逻辑设计设计思想： 采用邻接矩阵来存储图，然后采用克鲁斯卡尔算法求出最小生成树。构造体定义函数模块二求最小生成树克鲁斯卡尔算法函数模块一图的创立采用邻接矩阵做存储构造主函数引用函数模块一、二，实现算法设计1定义构造体。2采用邻接矩阵做存储构造创立图函数模块一。3采用克鲁斯卡尔算法求出该图的最小生成树函数模块二。4在主函数里面分别调用以上各个函数，最终实现设计目的。4详细设计4.1程序构造函数CreateMGraph用来实现图的创立，以及图的相关信息的存储。图的存储采用邻接矩阵存储构造。函数minitree_KRUSKAL 用来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是此题所要求使用的。各个函数间的联系先调用函数CreateMGraph实现图的创立，然后调用函数minitree_KRUSKAL求出该图的最小生成树4.2设计说明在开场的时候添加一些限制条件方便函数的功能实现例如：#define MaxVertexNum 100 /最大顶点个数#define QueueSize 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(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+);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; 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; printf(克鲁斯卡尔最小生成树：n);for (i=0;ie;i+) if (ei.flag=1) printf(%d,%d) %dn,ei.vexh,ei.vext,ei.weight);/输出最小生成树该步骤应用的是克鲁斯卡尔算法，它的根本思想是：每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边参加MSTMinimum Spanning Tree最小生成树，并将所在的2个连通分量合并，直到只剩一个连通分量。 流程如图4.2所示。. z.-图4.1图4.2. z.-5 程序编码#include #define MaxVertexNum 100 /最大顶点个数#define M 30typedef 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 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(请输入该图的顶点信息: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;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; 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;printf(n);printf(*n); printf(* 克鲁斯卡尔算法求图的最小生成树 *n);printf(*n); G=CreateMGraph();/建立该图的邻接矩阵minitree_KRUSKAL(&G);/克鲁斯卡尔算法最小生成树 return 0; . z.-6 程序调试与测试运行程序后如下图 图6.1输入错误数组后如下图 图6.2继续输入正确数组后如下图 图6.3. z.-7 结果分析程序运行时如果输入的点大于边减一再乘以边除以2，那就是说输入的数组是错误的，此时程序提醒输入错误，在重新输入。如果输入正确那么程序会输出最小生成树。. z.-8 总结这个程序运用函数CreateMGraph来实现图的创立，以及图的相关信息的存储。图的存储采用邻接矩阵存储构造。在运用函数minitree_KRUSKAL来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是此题所要求使用的。在整个程序中先调用函数CreateMGraph实现图的创立，然后调用函数minitree_KRUSKAL求出该图的最小生成树。这个程序实现了最小生成树的生成。在整个程序的设计过程中有太多的错误以及不懂的地方，虽然在最后完成了程序设计，但是我发现了我的更多的缺乏，在以后的学习中我会更加努力。. z.-参考文献1 严蔚敏，吴伟民.数据构造(C语言版)M.：清华大学,20022 春葆.数据构造(C语言版)习题与解析M. ：清华大学,20023 钱能.C+程序设计教程M. ：清华大学,2003. z.