普里姆算法求最小生成树课程设计报告.doc

课程设计成果 学院: 计算机工程学院 班 级: 计算机科学与技术 学生姓名: 学 号: 设计地点（单位）： 设计题目: 普里姆算法求最小生成树 完成日期： 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.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大模块，分别为采用邻接矩阵（表）的存储方式建立带权的（有）无向网络图和利用普里姆算法对所建的网络图求最小代生成树。它的最终目的是以最经济、最实惠、最节约的方式解决生活中的最短路径问题，以求给人们提供更节约、更便利的生活。在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。1.1系统目标根据课程设计题目的相关要求，应该完成以下目标：1.能够先生成一个网图，该网图既能是无向网图，有能是有向网图；2.要求分别采用邻接矩阵和链接表存储来完成；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语言描述普利姆算法生成最小生成树，所以可以使用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的邻接矩阵：图的邻接矩阵可利用两个数组实现，一个是一维数组，用来存储图中的顶点信息；另一个是二维数组，用来存储图中顶点之间的关系，该二维数组称为邻接矩阵。如图2.2所示图2.2 CreateMGraph()函数程序框图332.2.2普利姆函数程序框图普里姆算法中有多个循环，假设顶点的个数是n，则第一层循环的频度为n-1，第二层循环的频度为n，因此该算法的时间复杂度为O（n2），与网中的边数无关，因此普里姆算法适用于求边稠密的最小生成树。 如图2.3图2.3 prim函数2.2.3 createALgraph()函数程序框图定义整型i,j,k,w,输入顶点数和边数，执行循环读取顶点信息建立顶点表，将边表置为空表，建立空表，输入边（vi,vj）上的顶点序号，向内存申请空间生成表结点，将s的指针指向当前顶点上指向的结点，后将当前顶点的指针指向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 vexsMaxVertexNum; 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;typedef 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("请输入顶点数和边数："); scanf("%d,%d",&(G->n),&(G->e); printf("请输入顶点信息:"); for (i=0;i<G->n;i+) scanf("n%d",&(G->vexsi); for (i=0;i<G->n;i+) for (j=0;j<G->n;j+) if(i=j) G->edgesij=0; else G->edgesij=max; /*初始化邻接矩阵*/ printf("输入边对应的两个顶点的序号及权值："); for (k=0;k<G->e;k+) scanf("n%d,%d,%d",&i,&j,&weight); G->edgesij=weight; printf("输出顶点信息及邻接矩阵:n" ); OutPut(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;i<G->n;i+) scanf("n%d",&(G->vexsi); for (i=0;i<G->n;i+) for (j=0;j<G->n;j+) if(i=j) G->edgesij=0; else G->edgesij=max; /*初始化邻接矩阵*/ printf("输入边对应的两个顶点的序号及权值："); for (k=0;k<G->e;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%*c",&(g->n),&(g->e); printf("n输入顶点:"); for(i=0;i<g->n;i+) scanf("%d",&(g->adjlisti.vertex); g->adjlisti.firstedges=NULL; printf("n输入边和权值:"); for(k=0;k<g->e;k+) scanf("%d,%d,%d",&i,&j,&w); s=(edgenode*)malloc(sizeof(edgenode); s->adjvex=j; s->weight=w; s->next=g->adjlisti.firstedges; g->adjlisti.firstedges=s; DispAdjList(g);3.2.4创建无向网图邻接表存储void createALgraph(ALgraph *g) /*创建无向网图*/ int i,j,k,w; edgenode *s; printf("t=无向网图邻接表=n"); printf("输入顶点数和边数:"); scanf("%d,%d%*c",&(g->n),&(g->e); printf("n输入顶点:"); for(i=0;i<g->n;i+) scanf("%d",&(g->adjlisti.vertex); g->adjlisti.firstedges=NULL; printf("n输入边和权值:"); for(k=0;k<g->e;k+) scanf("%d,%d,%d",&i,&j,&w); s=(edgenode*)malloc(sizeof(edgenode); s->adjvex=j; s->weight=w; s->next=g->adjlisti.firstedges; g->adjlisti.firstedges=s; s=(edgenode*)malloc(sizeof(edgenode); s->adjvex=i; s->weight=w; s->next=g->adjlistj.firstedges; g->adjlistj.firstedges=s; DispAdjList(g);3.2.5 prim算法求最小生成树/*记录从顶点集合U到V-U的代价最小的边的数组定义*/typedef struct     VertexType adjvex;    VRType lowcost;closeedgeMaxSize;void MiniSpanTree_PRIM (MGraph G,VertexType u)/*利用普里姆算法求从第u个顶点出发构造网G的最小生成树T*/ int i,j,k; closeedge closedge; k=LocateVertex(G,u);/*k为顶点u对应的序号*/ for(j=0;j<G.vexnum;j+)/*数组初始化*/ strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arckj.adj; closedgek.lowcost=0;/*初始时集合U只包括顶点u*/ printf("最小代价生成树的各条边为:n"); for(i=1;i<G.vexnum;i+)/*选择剩下的G.vexnum-1个顶点*/ k=MiniNum(closedge,G);/*k为与U中顶点相邻接的下一个顶点的序号*/ printf("(%s-%s)n",closedgek.adjvex,G.vexk);/*输出生成树的边*/ closedgek.lowcost=0;/*第k顶点并入U集*/ for(j=0;j<G.vexnum;j+) if(G.arckj.adj<closedgej.lowcost)/*新顶点加入U集后重新将最小边存入到数组*/ strcpy(closedgej.adjvex,G.vexk); closedgej.lowcost=G.arckj.adj; 3.2.6输出邻接矩阵存储函数void OutPut (MGraph *G) int i,j; printf("tE= "); for (i=0;i<G->n;i+) printf("%d ",G->vexsi); printf(""); printf("n"); for(i=0;i<G->n;i+) for(j=0;j<G->n;j+) printf("t%d ",G->edgesij); printf("n"); 3.2.7输出邻接表存储函数void DispAdjList(ALgraph *g) int i; edgenode *p; printf("n网图的邻接表表示如下：n"); for (i=0; i<g->n; i+) printf("%d,%3d=>",i,g->adjlisti.vertex); p=g->adjlisti.firstedges; while (p!=NULL) printf("(%d,%d)->",p->adjvex,p->weight); p=p->next; printf("n"); 3.2.8邻接表转换成邻接矩阵函数void change(ALgraph *g) /*邻接表转换成邻接矩阵*/ int i,j; edgenode *p; graph *M;M=(graph*)malloc(sizeof(graph); M->n=g->n; M->e=g->e; for(i=0;i<M->e;i+) for(j=0;j<M->e;j+) if(i=j)M->edgesij=0; else M->edgesij=MaxVertexNum; for(i=0;i<g->n;i+) M->vexsi=g->adjlisti.vertex; for(i=0;i<g->n;i+) p=g->adjlisti.firstedges; while(p) M->edgesip->adjvex=p->weight; p=p->next; prim(M->edges,M->n,M->vexs);4 测试4.1调试准备选取包含六个顶点及10条边的图进行程序的测试，分别将需要测试的数据按要求键入，根据提示进行下级菜单的确定与选择，直到求解出测试数据的最小生成树。测试数据见图4.1及图4.2所示图4.1 测试数据图4.2 测试数据图4.2调试结果（1）以有向图邻接矩阵的方式输出最小生成树（图4.3、图4.4及图4.5）图 4.3图 4.4图 4.5（2） 以无向图邻接矩阵的方式输出最小生成树（图4.6、图4.7）图 4.6图 4.7（3） 以有向图邻接表的方式输出最小生成树（图4.8、图4.9）图 4.8图 4.9（4） 以无向图邻接表的方式输出最小生成树（图4.10、图4.11）图 4.10图 4.115 总结说明：本次课程设计由周德、舒胜、黄义、樊坤共同完成。其中邻接矩阵存储有向图、无向图及调用普里姆算法生成最小生成树、任务书填写由舒胜、樊坤完成；邻接表存储有向图、无向图及调用普里姆算法生成最小生成树、菜单界面由黄义完成；周德负责流程图绘制、文档排版等综合应用。通过此次课程设计，我对图的理解又上升了一个层次。数据结构这门课是非常奥妙的。图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系。正是这些奇妙的东西引发我在计算机科学这条大路上一直迸发前进，勇敢的去探索科学中未知而美妙的事。参考文献1李素若.数据结构（C语言描述）.2009，化学工业出版社. 2严蔚敏,吴伟民.数据结构（C语言描述）.1999,清华大学出版社. 3严蔚敏,吴伟民.数据结构题集(C语言版).1999，清华大学出版社.4严蔚敏,李冬梅,吴伟民.数据结构.2015.2，清华大学出版社. 5王晓东.数据结构(C语言描述).2011.11,电子工业出版社.附录 全部代码源程序：#include<stdio.h>#include<stdlib.h>#define MaxVertexNum 100#define max 1000typedef int VertexType;typedef int EdgeType;typedef struct VertexType vexsMaxVertexNum; EdgeType edgesMaxVertexNumMaxVertexNum; int n,e; MGraph;#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;typedef struct AdjList adjlist; int n,e;ALgraph;typedef int edgetype ;typedef struct edgetype vexsMaxVertexNum; edgetype edgesMaxVertexNumMaxVertexNum; int n,e; graph; void OutPut (MGraph *G) int i,j; printf("tE= "); for (i=0;i<G->n;i+) printf("%d ",G->vexsi); printf(""); printf("n"); for(i=0;i<G->n;i+) for(j=0;j<G->n;j+) printf("t%d ",G->edgesij); printf("n"); void prim(int gmMaxVertexNum ,int n,int closevertex ) /*普里姆算法*/ int lowcost100; int mincost; int i,j,k; for(i=0;i<n;i+) lowcosti=gm0i; closevertexi=0; lowcost0=0; closevertex0=0; for(i=1;i<n;i+) mincost=max; j=1; k=1; while(j<n) if(lowcostj<mincost&&lowcostj!=0) mincost=lowcostj; k=j; j+; printf("顶点的序号=%d 边的权值=%dn",k,mincost); lowcostk=0; for(j=0;j<n;j+) if(gmkj<lowcostj) lowcostj=gmkj; closevertexj=k; void CreateMGraph(MGraph *G)int i,j,k,weight;printf("t=有向网图邻接矩阵=n");printf("请输入顶点数和边数：");scanf("%d,%d",&(G->n),&(G->e);printf("请输入顶点信息:");for (i=0;i<G->n;i+) scanf("n%d",&(G->vexsi);for (i=0;i<G->n;i+)for (j=0;j<G->n;j+) if(i=j) G->edgesij=0; else G->edgesij=max; /*初始化邻接矩阵*/ printf("输入边对应的两个顶点的序号及权值："); for (k=0;k<G->e;k+) scanf("n%d,%d,%d",&i,&j,&weight); G->edgesij=weight; printf("输出顶点信息及邻接矩阵:n" ); OutPut(G); printf("输出最小生成树的信息:n"); prim(G->edges,G->n,G->vexs);void CreateGraph(MGraph *G) int i,j,k,weight; printf("t=无向网图邻接矩阵=n"); printf("请输入顶点数和边数："); scanf("%d,%d",&(G->n),&(G->e); printf("请输入顶点信息:"); for (i=0;i<G->n;i+) scanf("n%d",&(G->vexsi); for (i=0;i<G->n;i+)for (j=0;j<G->n;j+) if(i=j) G->edgesij=0; else G->edgesij=max;/*初始化邻接矩阵*/ printf("输入边对应的两个顶点的序号及权值："); for (k=0;k<G->e;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); void DispAdjList(ALgraph *g) int i; edgenode *p; printf("n网图的邻接表表示如下：n"); for (i=0; i<g->n; i+) printf("%d,%3d=>",i,g->adjlisti.vertex); p=g->adjlisti.firstedges; while (p!=NULL) printf("(%d,%d)->",p->adjvex,p->weight); p=p->next; printf("n"); void change(ALgraph *g) /*邻接表转换成邻接矩阵*/ int i,j; edgenode *p; graph *M;M=(graph*)malloc(sizeof(graph); M->n=g->n; M->e=g->e;for(i=0;i<M->e;i+) for(j=0;j<M->e;j+) if(i=j)M->edgesij=0; else M->edgesij=MaxVertexNum; for(i=0;i<g->n;i+) M->vexsi=g->adjlisti.vertex; for(i=0;i<g->n;i+) p=g->adjlisti.firstedges; while(p) M->edgesip->adjvex=p->weight; p=p->next; prim(M->edges,M->n,M->vexs); void createAgraph( ALgraph *g) /*创建有向网图*/ int i,j,k,w; edgenode *s; printf("t=有向网图邻接表=n"); printf("输入顶点数和边数:"); scanf("%d,%d%*c",&(g->n),&(g->e); printf("n输入顶点:"); for(i=0;i<g->n;i+) scanf("%d",&(g->adjlisti.vertex); g->adjlisti.firstedges=NULL; printf("n输入边和权值:"); for(k=0;k<g->e;k+) scanf("%d,%d,%d",&i,&j,&w); s=(edgenode*)malloc(sizeof(edgenode); s->adjvex=j; s->weight=w; s->next=g->adjlisti.firstedges; g->adjlisti.firstedges=s; DispAdjList(g); printf("输出最小生成树的信息:n"); change(g);void createALgraph(ALgraph *g) /*创建无向网图*/ int i,j,k,w; edgenode *s;printf("t=无向网图邻接表=n"); printf("输入顶点数和边数:"); scanf("%d,%d%*c",&(g->n),&(g->e); printf("n输入顶点:"); for(i=0;i<g->n;i+) scanf("%d",&(g->adjlisti.vertex); g->adjlisti.firstedges=NULL; printf("n输入边和权值:"); for(k=0;k<g->e;k+) scanf("%d,%d,%d",&i,&j,&w); s=(edgenode*)malloc(sizeof(edgenode); s->adjvex=j; s->weight=w; s->next=g->adjlisti