基于C语言的最小生成树kruskal算法问题

1、（最小生成树kruskal算法的实现）一。需求分析：题目：最小生成树kruskal算法的实现问题描述：任意创建一个图，用kruskal算法求去他的最小生成树。举例：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，我们可以用求kruskal算法求这个网的最小生成树来解决这个问题。（1） 建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值；（2）利用克鲁斯卡尔算法求网的最小生成树；（3）按顺序输出生成树中各条边以及它们的权值。输入的形式和输入值的范围：输入的数值有各顶点，

2、两顶点之间的权值。输入的顶点最多不能大于20个。输出的形式：先输出图的邻接矩阵，输出权值的排序，最后输出最小生成树的各边和权值。程序所能达到的功能；用户可以任意的输入一个顶点小于20的图，该程序可以求出图的邻接矩阵和最小生成树。d测试数据：6 5 1 2 1 2 3 2 3 4 3 4 5 4 1 5 6 3 2 4 5输出结果： v1, v2 1 v2, v3 2 v3, v4 3 v4,v5 4 二。概要分析 1 本程序中用到的所有抽象数据类型的定义adt graph 数据对象v：v是具有向他特性的数据元素的集合，称为顶点集。 数据关系对象： r=vrvr=|v.w且p（v,w）,表示v到

3、w的弧，谓词p（v，w）定义了弧的意义或信息 基本操作p： createcraph(&g,v,vr); 初始条件：v是图的顶点集，vr是图中的弧的集合。 操作结果：按v和vr的定义构造图g.minispantree(g);初始条件：图g存在。操作结果：求出图g的最小生成树sort(edge* ,mgraph *);初始条件：图g存在，edge存在。操作结果; 对edge进行了排序。swapn(edge *, int x, int y);初始条件：edge存在，x,y是两条边操作结果：交换了x,y这两条边。find(int *, int );初始条件：edge存在:操作结果：对这些边进行遍历查找

4、。2主程序的流程int main(void)/主函数 mgraph *g;程序中定义一个图g = (mgraph*)malloc(sizeof(mgraph);为这个图动态分配存储空间if (g = null)printf(memory allcation failed,goodbye);exit(1); 如果这个图不存在系统将会非正常结束 creatgraph(g);创建一个图输入总边数和总顶点输入各顶点和顶点之间的权值输出该图的邻接矩阵 minispantree(g);求该图的最小生成树 对权值进行排序输出排序后的权值和顶点对各边依次进行判断，是否存在回路，如果没有回路，则输出这条边，否则

5、，则不输出system(pause);程序运行暂停return 0;3序模块之间的层次（调用）关系 主函数模块图构建模块最小生成树模块3.详细设计#define m 20#define max 20规定该程序所能创建图的最大顶点数为20个点typedef struct /用结构体定义边edge;typedef struct/用结构体定义数组adjmatrixmaxmax;typedef struct/用结构体定义一个图mgraph; 函数申明 void creatgraph(mgraph *); /图构建函数申明 void sort(edge* ,mgraph *); /权值排序函数申明voi

6、d minispantree(mgraph *); /生成最小树函数的申明int find(int *, int );/ 尾顶点查找void swapn(edge *, int, int);/权值、头顶点、尾顶点交换void creatgraph(mgraph *g)/构件图printf(请输入边数和顶点数:n);g-arcij.adj = g-arcji.adj = 0;/先把矩阵中所有元素赋值为0for ( i = 1; i arcnum; i+)/输入边和权值 g-arcnm.adj = g-arcmn.adj = 1;/将输入的顶点记录为1getchar();printf(请输入%d与

7、%d之间的权值:n, n, m); printf(邻接矩阵为:n);输出邻接矩阵以上是图的创建，邻接矩阵的建立将辅助权值排序void minispantree(mgraph *g)/生成最小生成树 sort(edges, g);/sort函数调用，对权值进行排序void sort(edge edges,mgraph *g)/对权值进行排序 void swapn(edge *edges,int i, int j)/交换权值 以及头和尾 在对权值排序时，若(edgesi.weight edgesj.weigh)调用函数swapn交换这两条边的权值以及头和尾顶点 以上是对权值进行排序，排序之后将有利

8、于回路的判断，从而求出最小生成树 printf(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分 n = find(parent, edgesi.begin);m = find(parent, edgesi.end);if (n != m)/判断是否有回路，如果有，舍弃 parentm = n;printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);int find(int *parent, int f)/找尾 while ( parentf 0)f = parentf; return f; 关键代码输出最小生

9、成树以下是主函数部门int main(void)/主函数 mgraph *g;g = (mgraph*)malloc(sizeof(mgraph);if (g = null)printf(memory allcation failed,goodbye);exit(1); creatgraph(g); minispantree(g);system(pause);return 0;主函数通过调用不同的函数模块来实现的功能以下是函数关系的调用图 main( ) _ creatgraph() minispantree( ) _ sort ( ) find( ) swapn( )4.调试分析1由于对函数

10、调用关系不是非常清楚，导致在程序设计的时候思路不是非常的清晰2该程序只能满足图顶点比较少的最小生成树的实现，如果用户要求更大的空间，可以在创建图的时候开辟更大的空间。3在程序输入的时候，必须顶点数值小的先输入，否则程序将会出错。这也是程序应该改进的地方。4算法的时空分析 1，对矩阵的初始化，设输入一个n个顶点的图，那个将要对矩阵的nxn个元素进行初始化，所以时间复杂度为o(n2) 2,输入权值和边的时间复杂度为o(n),所以构建图的时间复杂度为o(n2+n) 3.矩阵输出的时间复杂度为o(n2) 。空间复杂度为s（n2） 4在求最小生成树函数中，对边进行标记的时间复杂度为o(n2)。对权值进行

11、排序的时间复杂度为o(n2)，对parent数组赋值的时间复杂度为o(n),所以该函数的时间复杂度为o（2n2+n）5 过这次课程设计，一方面我加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空分析等课程基本内容的理解，另一方面，使我在序设计方法（如抽象数据类型、结构化分析、模块化设计和结构化设计）、c语言程序调试和测试方面受到比较系统的严格的训练。 5.用户使用说明1,输入图的顶点数和变数2任意输入两个图中连接的顶点3输入这两个顶点的权值具体步骤图如下 输入完数据之后，按enter键将会显示以下结果 最后按任意键退出，可以进行其他图最小生成树的实现6.测试结

12、果这里提供其他几组测试数据：输入的数据： 输出数据输入数据： 输出数据：7.附录；源程序数据结构课程设计源代码（最小生成树kruskal算法的实现）学 院： 东方科技学院 班 级： 08级信息工程2班 学 号： 200841919234 姓 名： 谭诗琪 指导教师： 贺细平 #include#include#define m 20#define max 20typedef struct int begin; /头顶点int end; /末顶点int weight; /权值edge;typedef structint adj;int weight;/权值adjmatrixmaxmax;typed

13、ef structadjmatrix arc;int vexnum, arcnum;/顶点 弧mgraph; /函数申明 void creatgraph(mgraph *); /图构建 void sort(edge* ,mgraph *); /权值排序void minispantree(mgraph *); /生成最小树int find(int *, int );/ 尾顶点查找void swapn(edge *, int, int);/权值、头顶点、尾顶点交换void creatgraph(mgraph *g)/构件图int i, j,n, m;printf(请输入边数和顶点数:n);scan

14、f(%d %d,&g-arcnum,&g-vexnum); for (i = 1; i vexnum; i+)/初始化图for ( j = 1; j vexnum; j+)g-arcij.adj = g-arcji.adj = 0;for ( i = 1; i arcnum; i+)/输入边和权值 printf(请输入有边的2个顶点n);scanf(%d %d,&n,&m);while(n g-vexnum | m g-vexnum)printf(输入的数字不符合要求 请重新输入:n);scanf(%d%d,&n,&m);g-arcnm.adj = g-arcmn.adj = 1;getcha

15、r();printf(请输入%d与%d之间的权值:n, n, m);scanf(%d,&g-arcnm.weight); printf(邻接矩阵为:n);for ( i = 1; i vexnum; i+) for ( j = 1; j vexnum; j+)printf(%d ,g-arcij.adj);printf(n);void sort(edge edges,mgraph *g)/对权值进行排序 int i, j;for ( i = 1; i arcnum; i+)for ( j = i + 1; j arcnum; j+)if (edgesi.weight edgesj.weight

16、)swapn(edges, i, j); printf(权排序之后的为:n);for (i = 1; i arcnum; i+)printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);void swapn(edge *edges,int i, int j)/交换权值 以及头和尾 int temp; temp = edgesi.begin; edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.end = edgesj.end; edgesj.en

17、d = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edgesj.weight = temp;void minispantree(mgraph *g)/生成最小生成树 int i, j, n, m;int k = 1;int parentm;edge edgesm;for ( i = 1; i vexnum; i+)for (j = i + 1; j vexnum; j+)if (g-arcij.adj = 1)edgesk.begin = i;edgesk.end = j;edgesk.weight = g-arcij.weight;k+; sort(edges, g); for (i = 1; i arcnum; i+)parenti = 0; printf(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分 n = find(parent, edgesi.begin);m = find(parent, edgesi.end);if (n != m)/判断是否有回路，如果有，舍弃 parentm = n;printf( %dn, edgesi.begin,