《普里姆算法求最小生成树课程设计报告.doc》由会员分享，可在线阅读，更多相关《普里姆算法求最小生成树课程设计报告.doc（38页珍藏版）》请在金锄头文库上搜索。
1、 课程设计成果 学院: 计算机工程学院 班 级: 计算机科学与技术 学生姓名: 学 号: 设计地点（单位）： 设计题目: 普里姆算法求最小生成树 完成日期： 2016年 1月6日 指导教师评语: _ _成绩(五级记分制):_教师签名:_目录1 需求分析11.1系统目标11.2主体功能11.2开发环境12 概要设计22.1功能模块划分22.2系统流程图32.2.1 CreateMGraph()函数程序框图32.2.2普利姆函数程序框图42.2.3 createALgraph()函数程序框图52.2.4邻接矩阵Output()输出函数程序框图53 详细设计63.1数据结构63.2模块设计83.2.
2、1创建有向网图邻接矩阵存储83.2.2创建无向网图邻接矩阵存储93.2.3创建有向网图邻接表存储103.2.4创建无向网图邻接表存储113.2.5 prim算法求最小生成树123.2.6输出邻接矩阵存储函数133.2.7输出邻接表存储函数143.2.8邻接表转换成邻接矩阵函数144 测试154.1调试准备154.2调试结果165 总结21参考文献22附录 全部代码231 需求分析针对现实生活中，许多地方需要考虑到如：邮递员送信，在n个城市之间建立通信网络等最短路径的问题，本应用程序正是基于这一现实问题，在vc+的平台下，采用普里姆算法对此作出解决，本程序主要包含2大模块，分别为采用邻接矩阵（表
3、）的存储方式建立带权的（有）无向网络图和利用普里姆算法对所建的网络图求最小代生成树。它的最终目的是以最经济、最实惠、最节约的方式解决生活中的最短路径问题，以求给人们提供更节约、更便利的生活。在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。1.1系统目标根据课程设计题目的相关要求，应该完成以下目标：1.能够先生成一个网图，该网图既能是无向网图，有能是有向网图；2.要求分别采用邻接矩阵和链接表存储来完
4、成；3.最后打印输出最小生成树。1.2主体功能1.该程序会有菜单提示，可以根据需求进行选项：2.能够生成网图并确定其存储形式，且该网图可能为有向图也可能为无向图，并采用邻接表和邻接矩阵（起点、终点和权值）两种存储结构。3.可以建立带权图，并能够用Prim算法求该网图的最小生成树。1.2开发环境操作系统：Windows编译集成环境（IDE）：VC+6.0 Visual C+6.0（简称VC+6.0）是强大的C/C+软件开发工具，使用非常广泛，已经成为程序员首选的开发工具。利用它不仅可以开发控制台应用程序，还可以开发Windows SDK、MFC等应用程序。因为本课题主要利用C语言描述普利姆算法生
5、成最小生成树，所以可以使用Visual C+6.0开发控制台程序。 用Visual C+6.0编写C语言程序需要如下两个步骤，一是创建一个新的Viusal C+6.0控制台项目；二是在该项目中创建C程序文件，并编辑C语言程序。2 概要设计2.1功能模块划分该程序可输入的数据可为100以内的整数；可建立带权图，并能用Prim算法求该图的最小生成树，带菜单提示，可以根据需求进行选择：如图2.1所示。图2.1 主程序模块图2.2系统流程图2.2.1 CreateMGraph()函数程序框图建立图g的邻接矩阵：图的邻接矩阵可利用两个数组实现，一个是一维数组，用来存储图中的顶点信息；另一个是二维数组，用
6、来存储图中顶点之间的关系，该二维数组称为邻接矩阵。如图2.2所示图2.2 CreateMGraph()函数程序框图362.2.2普利姆函数程序框图普里姆算法中有多个循环，假设顶点的个数是n，则第一层循环的频度为n-1，第二层循环的频度为n，因此该算法的时间复杂度为O（n2），与网中的边数无关，因此普里姆算法适用于求边稠密的最小生成树。 如图2.3图2.3 prim函数2.2.3 createALgraph()函数程序框图定义整型i,j,k,w,输入顶点数和边数，执行循环读取顶点信息建立顶点表，将边表置为空表，建立空表，输入边（vi,vj）上的顶点序号，向内存申请空间生成表结点，将s的指针指向当
7、前顶点上指向的结点，后将当前顶点的指针指向s,如图2.4所示图2.4 CreateALgraph()函数2.2.4邻接矩阵Output()输出函数程序框图定义两个参数i，j，执行循环将指向之前存储到数组中的相关顶点和边之间的关系然后打印输出，如图2.5所示图2.5 邻接矩阵Output()输出函数3 详细设计3.1数据结构定义邻接矩阵邻接表数据结构#define MaxVertexNum 100#define max 1000typedef int VertexType;typedef int EdgeType;typedef struct VertexType vexsMaxVertexNu
8、m; EdgeType edgesMaxVertexNumMaxVertexNum; int n,e;MGraph;(1) 邻接表#define MaxVertexNum 100typedef int vertextype;typedef struct node int adjvex;int weight; struct node *next; edgenode;typedef struct vnode vertextype vertex; edgenode *firstedges; vertexnode;typedef vertexnode AdjListMaxVertexNum;typed
9、ef struct AdjList adjlist; int n,e;ALgraph;(3) 邻接表转换成邻接矩阵辅助结构体typedef int edgetype ;typedef struct edgetype vexsMaxVertexNum; edgetype edgesMaxVertexNumMaxVertexNum; int n,e; graph; /*邻接表转换成邻接矩阵辅助结构体*/3.2模块设计3.2.1创建有向网图邻接矩阵存储void CreateMGraph(MGraph *G) int i,j,k,weight; printf(t=有向网图邻接矩阵=n);printf(
10、请输入顶点数和边数：); scanf(%d,%d,&(G-n),&(G-e); printf(请输入顶点信息:); for (i=0;in;i+) scanf(n%d,&(G-vexsi); for (i=0;in;i+) for (j=0;jn;j+) if(i=j) G-edgesij=0; else G-edgesij=max; /*初始化邻接矩阵*/ printf(输入边对应的两个顶点的序号及权值：); for (k=0;ke;k+) scanf(n%d,%d,%d,&i,&j,&weight); G-edgesij=weight; printf(输出顶点信息及邻接矩阵:n ); Ou
11、tPut(G); printf(输出最小生成树的信息:n); prim(G-edges,G-n,G-vexs);3.2.2创建无向网图邻接矩阵存储void CreateGraph(MGraph *G) int i,j,k,weight; printf(t=无向网图邻接矩阵=n); printf(请输入顶点数和边数：); scanf(%d,%d,&(G-n),&(G-e); printf(请输入顶点信息:); for (i=0;in;i+) scanf(n%d,&(G-vexsi); for (i=0;in;i+) for (j=0;jn;j+) if(i=j) G-edgesij=0; els
12、e G-edgesij=max; /*初始化邻接矩阵*/ printf(输入边对应的两个顶点的序号及权值：); for (k=0;ke;k+) scanf(n%d,%d,%d,&i,&j,&weight); G-edgesij=weight; G-edgesji=weight; printf(输出顶点信息及邻接矩阵:n ); OutPut(G); printf(输出最小生成树的信息:n); prim(G-edges,G-n,G-vexs); 3.2.3创建有向网图邻接表存储void createAgraph( ALgraph *g) /*创建有向网图*/ int i,j,k,w; edgenode *s; printf(t=有向网图邻接表=n); printf(输入顶点数和边数:); scanf(%d,%d%*
