普里姆算法生成最小生成树_课程设计

《普里姆算法生成最小生成树_课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、JINGCHUUNIVERSITYOFTECHNOLOGY《数据结构（C语言描述）》课程设计学院计算机工程学院班级12级软件技术1班学号2012304040122、120124、133、121学生姓名周鑫、王彬彬、李松平张圣玮、魏远迎指导教师余云霞2014年1月3日目录1课程设计介绍11.1课程设计内容11.2课程设计要求12课程设计原理22.1课设题目粗略分析22.2原理图介绍32.2.1功能模块图32.2.2流程图分析33数据结构分析103.1存储结构103.2算法描述124调试与分析224.1调试过程224.2程序执行过程22参考文献28附录281课程设计介绍1.1课程设计内容编写

2、算法能够建立带权图，并能够用Prim算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。1.2课程设计要求1.可以输入顶点、边数及各路径的权值；2.通过建立无向图或有向图能过输出邻接矩阵或邻接表；3.可以输出建立的最小生成树；4.画出流程图，且函数有必要说明、注释；5.课设完成后上交报告及核心代码。第28页共29页2课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为两大模块。以下是两个模块的大体分析：1.创建网图并确定网图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用邻接表和邻接矩

3、阵（起点、终点和权值）两种存储结构，方便以后的编程。2.Prim算法。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树边的权值的集合。其思想是：令集合U的初值为U{u0}（即假设构造最小生成树时从结点u0开始），集合T 的初值为T={}。从所有结点u属于U和结点v属于V但不属于U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断重复，当U=V时，最小生成树便构造完毕。第28页共29页2.2原理图介绍2.2.1功能模块图显示菜单进行选择选择创建（有）无向图及存储方式有向图邻接矩阵无向图邻

4、接矩阵有向图邻接表无向图邻接表调用普里姆算法输出最小生成树结束开始图2.1功能模块图2.2.2流程图分析1.主函数第28页共29页开始显示菜单，选择输入1或2选择1选择2调用createAgraph()函数结束选择1调用CreateGraph()函数选择2调用CreateMGraph()函数调用createALgraph()函数调用Prim函数，输出最小生成树图2.2主函数流程图2.CreateMGraph()函数第28页共29页开始inti,j,kfor(i=0;in;i++)scanf(“%c”,&(G->vexs[i]));for(i=0;in;i++)for(

5、j=0;in;i++)i=jG->edges[i][j]=0;YNG->edges[i][j]=max;for(k=0;ke;k++)scanf("%d,%d,%d",&i,&j,&weight);G->edges[i][j]=weight;OutPut(G);prim(G->edges,G->n,G->vexs);结束图2.3CreateMGraph()函数流程图第28页共29页3．Prim()函数开始inti,j,k,lowcost[100],mincost;for(i=1;i

6、;}set[i]=0;i=1;j=1;YYlowcost[0]=0;closevertex[0]=0;for(i=1;i

7、流程图第28页共29页4.createALgraph()函数开始inti,j,k,w;edgenode*s;scanf("%d,%d%*c",&(g->n),&(g->e));for(i=0;in;i++)scanf("%d",&(g->adjlist[i].vertex));g->adjlist[i].firstedges=NULL;for(k=0;ke;k++)scanf("%d,%d,%d",&i,&j,&w)