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

课程设计成果学院:计算机工程学院班级:计算机科学与技术学生姓名:学号:设计地点（单位）：设计题目:普里姆算法求最小生成树完成日期：2016年1月6日指导教师评语:__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________成绩(五级记分制):_____________________教师签名:_____________________________ 目录1需求分析 需求分析针对现实生活中，许多地方需要考虑到如：邮递员送信，在n个城市之间建立通信网络等最短路径的问题，本应用程序正是基于这一现实问题，在vc++的平台下，采用普里姆算法对此作出解决，本程序主要包含2大模块，分别为采用邻接矩阵（表）的存储方式建立带权的（有）无向网络图和利用普里姆算法对所建的网络图求最小代生成树。它的最终目的是以最经济、最实惠、最节约的方式解决生活中的最短路径问题，以求给人们提供更节约、更便利的生活。在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。1.1系统目标根据课程设计题目的相关要求，应该完成以下目标：1.能够先生成一个网图，该网图既能是无向网图，有能是有向网图；2.要求分别采用邻接矩阵和链接表存储来完成；3.最后打印输出最小生成树。1.2主体功能1.该程序会有菜单提示，可以根据需求进行选项：2.能够生成网图并确定其存储形式，且该网图可能为有向图也可能为无向图，并采用邻接表和邻接矩阵（起点、终点和权值）两种存储结构。3.可以建立带权图，并能够用Prim算法求该网图的最小生成树。1.2开发环境操作系统：Windows编译集成环境（IDE）：VC++6.0VisualC++6.0（简称VC++6.0）是强大的C/C++软件开发工具，使用非常广泛，已经成为程序员首选的开发工具。利用它不仅可以开发控制台应用程序，还可以开发WindowsSDK、MFC等应用程序。因为本课题主要利用C语言描述普利姆算法生成最小生成树，所以可以使用VisualC++6.0开发控制台程序。用VisualC++6.0编写C语言程序需要如下两个步骤，一是创建一个新的ViusalC++6.0控制台项目；二是在该项目中创建C程序文件，并编辑C语言程序。2概要设计2.1功能模块划分该程序可输入的数据可为100以内的整数；可建立带权图，并能用Prim算法求该图的最小生成树，带菜单提示，可以根据需求进行选择：如图2.1所示。图2.1主程序模块图2.2系统流程图2.2.1CreateMGraph()函数程序框图建立图g的邻接矩阵：图的邻接矩阵可利用两个数组实现，一个是一维数组，用来存储图中的顶点信息；另一个是二维数组，用来存储图中顶点之间的关系，该二维数组称为邻接矩阵。如图2.2所示图2.2CreateMGraph()函数程序框图2.2.2普利姆函数程序框图普里姆算法中有多个循环，假设顶点的个数是n，则第一层循环的频度为n-1，第二层循环的频度为n，因此该算法的时间复杂度为O（n2），与网中的边数无关，因此普里姆算法适用于求边稠密的最小生成树。如图2.3图2.3prim函数2.2.3createALgraph()函数程序框图定义整型i,j,k,w,输入顶点数和边数，执行循环读取顶点信息建立顶点表，将边表置为空表，建立空表，输入边（vi,vj）上的顶点序号，向内存申请空间生成表结点，将s的指针指向当前顶点上指向的结点，后将当前顶点的指针指向s,如图2.4所示图2.4CreateALgraph()函数2.2.4邻接矩阵Output()输出函数程序框图定义两个参数i，j，执行循环将指向之前存储到数组中的相关顶点和边之间的关系然后打印输出，如图2.5所示图2.5邻接矩阵Output()输出函数3详细设计3.1数据结构定义邻接矩阵邻接表数据结构#defineMaxVertexNum100#definemax1000typedefintVertexType;typedefintEdgeType;typedefstruct{VertexTypevexs[MaxVertexNum];EdgeTypeedges[MaxVertexNum][MaxVertexNum];intn,e;}MGraph;邻接表#defineMaxVertexNum100typedefintvertextype;typedefstructnode{intadjvex; intweight;structnode*next;}edgenode;typedefstructvnode{vertextypevertex;edgenode*firstedges;}vertexnode;typedefvertexnodeAdjList[MaxVertexNum];typedefstruct{AdjListadjlist;intn,e;}ALgraph;邻接表转换成邻接矩阵辅助结构体typedefintedgetype;typedefstruct{edgetypevexs[MaxVertexNum];edgetypeedges[MaxVertexNum][MaxVertexNum];intn,e;}graph;/*邻接表转换成邻接矩阵辅助结构体*/3.2模块设计3.2.1创建有向网图邻接矩阵存储voidCreateMGraph(MGraph*G){inti,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->vexs[i]));for(i=0;i<G->n;i++)for(j=0;j<G->n;j++) {if(i==j)G->edges[i][j]=0;elseG->edges[i][j]=max; }/*初始化邻接矩阵*/printf("输入边对应的两个顶点的序号及权值：");for(k=0;k<G->e;k++){scanf("\n%d,%d,%d",&i,&j,&weight);G->edges[i][j]=weight;}printf("输出顶点信息及邻接矩阵:\n");OutPut(G);printf("输出最小生成树的信息:\n");prim(G->edges,G->n,G->vexs);}3.2.2创建无向网图邻接矩阵存储voidCreateGraph(MGraph*G){inti,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->vexs[i]));for(i=0;i<G->n;i++)for(j=0;j<G->n;j++) {if(i==j)G->edges[i][j]=0;elseG->edges[i][j]=max; }/*初始化邻接矩阵*/printf("输入边对应的两个顶点的序号及权值：");for(k=0;k<G->e;k++){scanf("\n%d,%d,%d",&i,&j,&weight);G->edges[i][j]=weight; G->edges[j][i]=weight;}printf("输出顶点信息及邻接矩阵:\n");OutPut(G);printf("输出最小生成树的信息:\n");prim(G->edges,G->n,G->vexs);}3.2.3创建有向网图邻接表存储voidcreateAgraph(ALgraph*g)/*创建有向网图*/{inti,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->adjlist[i].vertex));g->adjlist[i].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->adjlist[i].firstedges;g->adjlist[i].firstedges=s;}DispAdjList(g);}3.2.4创建无向网图邻接表存储voidcreateALgraph(ALgraph*g)/*创建无向网图*/{inti,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->adjlist[i].vertex));g->adjlist[i].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->adjlist[i].firstedges;g->adjlist[i].firstedges=s;s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;s->weight=w;s->next=g->adjlist[j].firstedges;g->adjlist[j].firstedges=s;}DispAdjList(g);}3.2.5prim算法求最小生成树/*记录从顶点集合U到V-U的代价最小的边的数组定义*/

typedef

struct

{

VertexTypeadjvex;

VRType

lowcost;

}closeedge[MaxSize];voidMiniSpanTree_PRIM(MGraphG,VertexTypeu)/*利用普里姆算法求从第u个顶点出发构造网G的最小生成树T*/{inti,j,k;closeedgeclosedge;k=LocateVertex(G,u);/*k为顶点u对应的序号*/for(j=0;j<G.vexnum;j++)/*数组初始化*/{strcpy(closedge[j].adjvex,u);closedge[j].lowcost=G.arc[k][j].adj;}closedge[k].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",closedge[k].adjvex,G.vex[k]);/*输出生成树的边*/closedge[k].lowcost=0;/*第k顶点并入U集*/for(j=0;j<G.vexnum;j++)if(G.arc[k][j].adj<closedge[j].lowcost)/*新顶点加入U集后重新将最小边存入到数组*/{strcpy(closedge[j].adjvex,G.vex[k]);closedge[j].lowcost=G.arc[k][j].adj;}}}3.2.6输出邻接矩阵存储函数voidOutPut(MGraph*G){inti,j;printf("\tE={");for(i=0;i<G->n;i++)printf("%d",G->vexs[i]);printf("}");printf("\n");for(i=0;i<G->n;i++){for(j=0;j<G->n;j++)printf("\t%d",G->edges[i][j]);printf("\n");}}3.2.7输出邻接表存储函数voidDispAdjList(ALgraph*g){inti;edgenode*p;printf("\n网图的邻接表表示如下：\n");for(i=0;i<g->n;i++){printf("[%d,%3d]=>",i,g->adjlist[i].vertex);p=g->adjlist[i].firstedges;while(p!=NULL){printf("(%d,%d)->",p->adjvex,p->weight);p=p->next;}printf("^\n");}}3.2.8邻接表转换成邻接矩阵函数voidchange(ALgraph*g)/*邻接表转换成邻接矩阵*/{inti,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->edges[i][j]=0;elseM->edges[i][j]=MaxVertexNum;for(i=0;i<g->n;i++)M->vexs[i]=g->adjlist[i].vertex;for(i=0;i<g->n;i++){p=g->adjlist[i].firstedges;while(p){M->edges[i][p->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以无向图邻接矩阵的方式输出最小生成树（图4.6、图4.7）图4.6图4.7以有向图邻接表的方式输出最小生成树（图4.8、图4.9）图4.8图4.9以无向图邻接表的方式输出最小生成树（图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>#defineMaxVertexNum100#definemax1000typedefintVertexType;typedefintEdgeType;typedefstruct{VertexTypevexs[MaxVertexNum];EdgeTypeedges[MaxVertexNum][MaxVertexNum];intn,e;}MGraph;#defineMaxVertexNum100typedefintvertextype;typedefstructnode{intadjvex;intweight;structnode*next;}edgenode;typedefstructvnode{vertextypevertex;edgenode*firstedges;}vertexnode;typedefvertexnodeAdjList[MaxVertexNum];typedefstruct{AdjListadjlist;intn,e;}ALgraph;typedefintedgetype;typedefstruct{edgetypevexs[MaxVertexNum];edgetypeedges[MaxVertexNum][MaxVertexNum];intn,e;}graph;voidOutPut(MGraph*G){inti,j;printf("\tE={");for(i=0;i<G->n;i++)printf("%d",G->vexs[i]);printf("}");printf("\n");for(i=0;i<G->n;i++){for(j=0;j<G->n;j++)printf("\t%d",G->edges[i][j]);printf("\n");}}voidprim(intgm[][MaxVertexNum],intn,intclosevertex[]){/*普里姆算法*/intlowcost[100];intmincost;inti,j,k;for(i=0;i<n;i++){lowcost[i]=gm[0][i];closevertex[i]=0;}lowcost[0]=0;closevertex[0]=0;for(i=1;i<n;i++){mincost=max;j=1;k=1;while(j<n){if(lowcost[j]<mincost&&lowcost[j]!=0){mincost=lowcost[j];k=j;}j++;}printf("顶点的序号=%d边的权值=%d\n",k,mincost);lowcost[k]=0;for(j=0;j<n;j++)if(gm[k][j]<lowcost[j]){lowcost[j]=gm[k][j];closevertex[j]=k;}}}voidCreateMGraph(MGraph*G){ inti,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->vexs[i])); for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) { if(i==j)G->edges[i][j]=0; elseG->edges[i][j]=max; }/*初始化邻接矩阵*/printf("输入边对应的两个顶点的序号及权值："); for(k=0;k<G->e;k++) { scanf("\n%d,%d,%d",&i,&j,&weight); G->edges[i][j]=weight;}printf("输出顶点信息及邻接矩阵:\n");OutPut(G);printf("输出最小生成树的信息:\n");prim(G->edges,G->n,G->vexs);}voidCreateGraph(MGraph*G){inti,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->vexs[i])); for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) {if(i==j)G->edges[i][j]=0; elseG->edges[i][j]=max; }/*初始化邻接矩阵*/printf("输入边对应的两个顶点的序号及权值：");for(k=0;k<G->e;k++){scanf("\n%d,%d,%d",&i,&j,&weight);G->edges[i][j]=weight; G->edges[j][i]=weight;}printf("输出顶点信息及邻接矩阵:\n");OutPut(G);printf("输出最小生成树的信息:\n");prim(G->edges,G->n,G->vexs);}voidDispAdjList(ALgraph*g){inti;edgenode*p;printf("\n网图的邻接表表示如下：\n");for(i=0;i<g->n;i++){printf("[%d,%3d]=>",i,g->adjlist[i].vertex);p=g->adjlist[i].firstedges;while(p!=NULL){printf("(%d,%d)->",p->adjvex,p->weight);p=p->next;}printf("^\n");}}voidchange(ALgraph*g)/*邻接表转换成邻接矩阵*/{inti,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->edges[i][j]=0;elseM->edges[i][j]=MaxVertexNum;for(i=0;i<g->n;i++)M->vexs[i]=g->adjlist[i].vertex;for(i=0;i<g->n;i++){p=g->adjlist[i].firstedges;while(p){M->edges[i][p->adjvex]=p->weight;p=p->next;}}prim(M->edges,M->n,M->vexs);}voidcreateAgraph(ALgraph*g)/*创建有向网图*/{inti,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->adjlist[i].vertex));g->adjlist[i].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->adjlist[i].firstedges;g->adjlist[i].firstedges=s;}DispAdjList(g);printf("输出最小生成树的信息:\n");change(g);}voidcreateALgraph(ALgraph*g)/*创建无向网图*/{inti,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->adjlist[i].vertex));g->adjlist[i].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->adjlist[i].firstedges;g->adjlist[i].firstedges=s;s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;s->weight=w;s->next=g->adjlist[j].firstedges;g->adjlist[j].firstedges=s;}DispAdjList(g);printf("输出最小生成树的信息:\n");change(g);}intmain(){ intgraphtype,storagetype; ALgraphg; MGraphG;printf("**************************************************************\n");printf("选择创建图的类型（键入相应数字进行创建）\n");printf("1、创建有向图\n");printf("2、创建无向图\n");printf("**************************************************************\n");printf("请选择：");scanf("%d",&graphtype);printf("**************************************************************\n");printf("请选择图存储类型（键入相应数字进行创建）\n");printf("1、邻接表\n");printf("2、邻接矩阵\n");printf("**************************************************************\n");printf("请选择：");scanf("%d",&storagetype);printf("**************************************************************\n");if(graphtype==1){ if(storagetype==1) { createAgraph(&g); } elseif(storagetype==2) { CreateMGraph(&G); }}if(graphtype==2){ if(storagetype==1) { createALgraph(&g); } elseif(storagetype==2) { CreateGraph(&G); }}}基于C8051F单片机直流电动机反馈控制系统的设计与研究目录1需求分析 11.1系统目标 11.2主体功能 11.2开发环境 12概要设计 22.1功能模块划分 22.2系统流程图 32.2.1CreateMGraph()函数程序框图 32.2.2普利姆函数程序框图 42.2.3createALgraph()函数程序框图 52.2.4邻接矩阵Output()输出函数程序框图 53详细设计 63.1数据结构 63.2模块设计 83.2.1创建有向网图邻接矩阵存储 83.2.2创建无向网图邻接矩阵存储 93.2.3创建有向网图邻接表存储 103.2.4创建无向网图邻接表存储 113.2.5prim算法求最小生成树 123.2.6输出邻接矩阵存储函数 133.2.7输出邻接表存储函数 143.2.8邻接表转换成邻接矩阵函数 144测试 154.1调试准备 154.2调试结果 165总结 21参考文献 22附录全部代码 23目录TOC\o"1-3"\f\h\u15739第一章总论 452391.1项目概述 4108251.2项目提出的背景和必要性 4177201.3项目建设的可行性分析 166440第二章项目依据和范围 20167162.1项目编制依据 20262292.2编制原则 20168752.3项目编制范围 21HYPERLINK\l_T