prim_和kruskal_算法分析课程设计代码

1、一、设计目的1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、设计内容问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。基本要求：(1)建立n个城市的连通图；(2)设计其存储结构；(3)显示所建立的图；用Prim 和Kruskal两种方法实现求最经济的架设方法，即求解最小生成数 ，显示两种方法产生的树中包含的每条边。三

2、设计要求1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。

3、详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。5.程序调试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 7.编写课程设计说明书。四、设计过程1、算法思想分析（1）P

4、rim算法求最小生成树的主要思想：此算法是普利姆与1957年提出的一种构造最小生成树的算法，主要思想是：假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从U=u0( u0V),TE=开始，重复执行下述操作：在所有uU,vV-U的边（u,v）E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，E）为N的最小生成树。对于最小生成树问题最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。（2）kruskal算法求最小生成树的主要思想及分析：Kruskall算法每

5、次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 七个城市的连通图如下：流程图 开始输入城市及边的个数输入起点终点权值邻接矩阵存储N最小权值Y输出邻接矩阵最小生成树 结束2、算法描述与实现Prim算法描述：通过邻接矩阵的建立，可以将任意两点的权值存入其中，便于进行各边的权值的比较修改，

6、在普利姆算法中，为实现这个算法需附设一个辅助数组closedge，以记录从U到V-U具有最小代价的边，对每个顶点viV-U,在辅助数组中存在一个相应分量closedgei-1，他包括两个域，其中lowcost存储该边上的权值。显然，closedgei-1.lowcost=Mincost(u,vi)| uU从算法可以看出每加入一个顶点到U中，closedge数组都会发生相应的变化。程序模块之间的调用：在主函数中调用邻接矩阵的初始化函数，邻接矩阵的生成函数，PRIM算法的函数，图的构造函数，输出函数。邻接矩阵的生成函数主要解决的是边的信息存储问题，而PRIM算法的函数是解决计算出最小生成树的功能。

7、Prim算法的实现及分析： prim的函数用来用Prim算法求最小生成树void prim(int gmax,int n) int lowcostmax,closestmax; int i,j,k,min; for(i=2;i<=n;i+) / n个顶点，n-1条边 lowcosti=g1i; closesti=1; / 顶点未加入到最小生成树中 lowcost1=0; / 标志顶点1加入U集合 for(i=2;i<=n;i+) / 形成n-1条边的生成树 min=inf; k=0; for(j=2;j<=n;j+) / 寻找满足边的一个顶点在U,另一个顶点 if(lowco

8、stj<min)&&(lowcostj!=0) min=lowcostj; k=j; printf("(%d,%d)%dt",closestk,k,min); for(j=2;j<=n;j+) if(gkj<lowcostj) lowcostj=gkj; closestj=k; printf("n"); 建立无向图并初始化矩阵的函数如下int adjg(int gmax) int n,e,i,j,k,v1,v2,weight; printf("输入城市个数，边的条数(用逗号隔开且用数字代表城市)：")

9、; scanf("%d,%d",&n,&e); if(n>e)printf("请重新输入城市个数，边的条数(用逗号隔开且用数字代表城市)：");scanf("%d,%d",&n,&e); for(i=1;i<=n;i+) for(j=1;j<=n;j+) gij=inf; / 初始化矩阵，全部元素设为无穷大 for(k=1;k<=e;k+) printf("输入第%d条边的起点城市，终点城市，权值:",k); scanf("%d,%d,%d"

10、;,&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n);用邻接矩阵存放无向图并输出邻接矩阵的函数如下void prg(int gmax,int n) int i,j; for(i=0;i<=n;i+) printf("%dt",i); for(i=1;i<=n;i+) printf("n%dt",i); for(j=1;j<=n;j+) printf(gij=inf)?"t":"%dt",gij); printf(

11、"n");Kruskal算法描述与实现Kruskal算法描述：假设 WN=(V,E) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止

12、。Kruskal算法实现及分析： 函数申明部分typedef struct int begin; int end; int weight;edge;typedef struct int adj; int weight;AdjMatrixMAXMAX;typedef struct AdjMatrix arc; int vexnum, arcnum;MGraph;void CreatGraph(MGraph *); void sort(edge* ,MGraph *);void MiniSpanTree(MGraph *);int Find(int *, int );void Swapn(edge

13、 *, int, int);构建邻接矩阵来存放个城市及它们之间的权值并输出邻接矩阵void CreatGraph(MGraph *G) int i, j,n, m; printf("请输入边数和城市顶点数:"); scanf("%d %d",&G->arcnum,&G->vexnum); for (i = 1; i <= G->vexnum; i+) /初始化图 for ( j = 1; j <= G->vexnum; j+) G->arcij.adj = G->arcji.adj = 0;

14、 for ( i = 1; i <= G->arcnum; i+) /输入边和权值 printf("n请输入有边的2个城市顶点（用数字表示）"); scanf("%d %d",&n,&m); while(n < 0 | n > G->vexnum | m < 0 | n > G->vexnum) printf("输入的数字不符合要求 请重新输入:"); scanf("%d%d",&n,&m); G->arcnm.adj = G-&

15、gt;arcmn.adj = 1; getchar(); printf("n请输入%d与%d之间的权值:", n, m); scanf("%d",&G->arcnm.weight); printf("邻接矩阵为:n"); for ( i = 1; i <= G->vexnum; i+) for ( j = 1; j <= G->vexnum; j+) printf("%d ",G->arcij.adj); printf("n"); 对权值进行排序 以便

16、求最小生成树使用 void sort(edge edges,MGraph *G) int i, j; for ( i = 1; i < G->arcnum; i+) for ( j = i + 1; j <= G->arcnum; j+) if (edgesi.weight > edgesj.weight) Swapn(edges, i, j); printf("权排序之后的为:n"); for (i = 1; i < G->arcnum; i+) printf("<< %d, %d >> %dn&

17、quot;, 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.end = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edges

18、j.weight = temp;用Kruskal算法求最小生成树void MiniSpanTree(MGraph *G) /生成最小生成树 int i, j, n, m; int k = 1; int parentM; edge edgesM; for ( i = 1; i < G->vexnum; i+) for (j = i + 1; j <= G->vexnum; j+) if (G->arcij.adj = 1) edgesk.begin = i; edgesk.end = j; edgesk.weight = G->arcij.weight; k+

19、; sort(edges, G); for (i = 1; i <= G->arcnum; i+) parenti = 0; printf("最小生成树为:n"); for (i = 1; i <= G->arcnum; i+) /核心部分 n = Find(parent, edgesi.begin); m = Find(parent, edgesi.end); if (n != m) parentn = m; printf("<< %d, %d >> %dn", edgesi.begin, edgesi.

20、end, edgesi.weight); int Find(int *parent, int f) /找尾 while ( parentf > 0) f = parentf; return f;3、系统测试用Prim算法测试连通图并求最小生成树：界面的截图：输入城市个数和边的条数情况的截图：输入错误情况下的截图：输出结果的截图用Kruskal算法测试连通图并求最小生成树：界面的截图：输入情况的截图：输入错误情况下的截图：输出结果的截图：五、设计总结 我们设计的题目是最小生成树的构造，在这次实践中遇到了各种问题，碰到问题有时总是百思不得其解最开始，程序要求输入数值时，如果任意没有按照程序给

21、定的类型输入，程序就会出现死循环，虽然加入了检测程序段，但是当我们不按个数输入的时候程序也出现了不稳定，又进入死循环了。我们想了很多办法，其中之一就是加入break这个函数。不过，并没有出项我们想要的结果，导致循环检测输入的函数while无法继续执行，中途就中断了。有点大失所望，但是我们没有气馁。记得以前老是又用过清空缓存这个函数，会不会失这个原因呢？经过我们反复测试，最终确定原因，正是出在这里，导致数据无法更新。最小生成树主要由PRIM算法完成，由于老师平时课上对普利姆算法和克鲁斯卡尔算法的知识的透彻讲解，通过整体构思，于是，我们先确立了基本步骤：1.建立一个具有n个定点的无向图 2.接着创

22、建一个邻接矩阵来存储该图，然后初始化该矩阵，最后根据普利姆算法和克鲁斯卡尔算法，得到了最小生成树以及各边的权值 ；好的开头是成功的一半，按照这个步骤，我们忙碌了3天，在大家的共同努力下，我们总算将此程序设计出来。尽管不是自己独立完成，但仍然很欣慰，因为在设计的过程中，让我们了解到要设计一个大型程序，查找资料是至关重要的，在他人的基础上，再根据自己所学进行修改与调试，最后设计出自己想要的程序，这过程艰辛，但只要你持之以恒，定可将问题解决。 通过本次实验巩固了课本的基本知识，熟练运用课程知识。提高我们组织数据及编写程序的能力，使我们能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中

23、的问题在计算机内部表示出来并用软件解决问题，本次实验大大提高了对编程的爱好，发现，只要认认真真的去思考，没有办不到的事情， 程序设计过程有 参考文献：数据结构程序设计题典李春葆等编 清华大学出版社数据结构(C语言版) 黄国瑜 叶乃菁编 清华大学出版社数据结构课程设计苏仕华 等编 机械工业出版社 附录Prim算法代码#include <stdio.h>#define inf 9999#define max 40void prim(int gmax,int n) / prim的函数 int lowcostmax,closestmax; int i,j,k,min; for(i=2;i&

24、lt;=n;i+) / n个顶点，n-1条边 lowcosti=g1i; / 初始化 closesti=1; / 顶点未加入到最小生成树中 lowcost1=0; / 标志顶点1加入U集合 for(i=2;i<=n;i+) / 形成n-1条边的生成树 min=inf; k=0; for(j=2;j<=n;j+) / 寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostj<min)&&(lowcostj!=0) min=lowcostj; k=j; printf("(%d,%d)%dt",closestk,k,min); l

25、owcostk=0; / 顶点k加入U for(j=2;j<=n;j+) / 修改由顶点k到其他顶点边的权值 if(gkj<lowcostj) lowcostj=gkj; closestj=k; printf("n"); int adjg(int gmax) / 建立无向图 int n,e,i,j,k,v1,v2,weight; printf("输入城市个数，边的条数(用逗号隔开且用数字代表城市)："); scanf("%d,%d",&n,&e); for(i=1;i<=n;i+) for(j=1;j

26、<=n;j+) gij=inf; / 初始化矩阵，全部元素设为无穷大 for(k=1;k<=e;k+) printf("输入第%d条边的起点城市，终点城市，权值:",k); scanf("%d,%d,%d",&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; return(n);void prg(int gmax,int n) / 输出无向图的邻接矩阵 int i,j; for(i=0;i<=n;i+) printf("%dt",i); for(i=1;

27、i<=n;i+) printf("n%dt",i); for(j=1;j<=n;j+) printf(gij=inf)?"t":"%dt",gij); printf("n");void main() int gmaxmax,n; n=adjg(g); printf("输入无向图的邻接矩阵:n"); prg(g,n); printf("最小生成树的构造:n"); prim(g,n); Kruskal算法代码#include<stdio.h>#includ

28、e<stdlib.h>#define M 20#define MAX 20typedef struct  int begin; int end; int weight;edge;typedef struct int adj; int weight;AdjMatrixMAXMAX;typedef struct AdjMatrix arc; int vexnum, arcnum;MGraph;void CreatGraph(MGraph *);/函数申明 void sort(edge* ,MGra

29、ph *);void MiniSpanTree(MGraph *);int  Find(int *, int );void Swapn(edge *, int, int);void CreatGraph(MGraph *G)/构件图 int i, j,n, m; printf("请输入边数和城市顶点数:"); scanf("%d %d",&G->arcnum,&G->vexnum);     for (i = 1; i <= G->ve

30、xnum; i+)/初始化图   for ( j = 1; j <= G->vexnum; j+)     G->arcij.adj = G->arcji.adj = 0;    for ( i = 1; i <= G->arcnum; i+)/输入边和权值    printf("n请输入有边的2个城市顶点（用数字表示）");  scanf("%d %

31、d",&n,&m);  while(n < 0 | n > G->vexnum | m < 0 | n > G->vexnum)     printf("输入的数字不符合要求 请重新输入:");   scanf("%d%d",&n,&m);         G->arcnm.adj =

32、 G->arcmn.adj = 1;  getchar();  printf("n请输入%d与%d之间的权值:", n, m);  scanf("%d",&G->arcnm.weight);      printf("邻接矩阵为:n"); for ( i = 1; i <= G->vexnum; i+)    for ( j = 1;

33、j <= G->vexnum; j+)        printf("%d ",G->arcij.adj);       printf("n"); void sort(edge edges,MGraph *G)/对权值进行排序  int i, j; for ( i = 1; i < G->arcnum; i+)   for (

34、j = i + 1; j <= G->arcnum; j+)     if (edgesi.weight > edgesj.weight)       Swapn(edges, i, j);           printf("权排序之后的为:n"); for (i = 1; i < G->arcnum; i

35、+)      printf("<< %d, %d >>   %dn", edgesi.begin, edgesi.end, edgesi.weight); void Swapn(edge *edges,int i, int j)/交换权值 以及头和尾     int temp;      temp = edgesi.begin;   

36、;   edgesi.begin = edgesj.begin;    edgesj.begin = temp;    temp = edgesi.end;      edgesi.end = edgesj.end;    edgesj.end = temp;    temp = edgesi.weight;      edgesi.weight = edg

37、esj.weight;    edgesj.weight = temp;void MiniSpanTree(MGraph *G)/生成最小生成树  int i, j, n, m; int k = 1;    int parentM; edge edgesM;  for ( i = 1; i < G->vexnum; i+)   for (j = i + 1; j <= G->vexnum; j+)     if (G->arcij.adj = 1)       edgesk.begin = i;