《普里姆算法生成小生成树课程设计(DOC 32页)》由会员分享，可在线阅读，更多相关《普里姆算法生成小生成树课程设计(DOC 32页)（32页珍藏版）》请在金锄头文库上搜索。
1、普里姆算法生成小生成树课程设计JINGCHU UNIVERSITY OF TECHNOLOGY数据结构（C语言描述）课程设计学 院 计算机工程学院 班 级 12级软件技术1班 学 号 2012304040122、120 124、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 调试
2、过程224.2程序执行过程22参考文献28附 录28 1 课程设计介绍1.1 课程设计内容 编写算法能够建立带权图，并能够用Prim算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。1.2 课程设计要求1. 可以输入顶点、边数及各路径的权值；2. 通过建立无向图或有向图能过输出邻接矩阵或邻接表；3. 可以输出建立的最小生成树；4. 画出流程图，且函数有必要说明、注释；5. 课设完成后上交报告及核心代码。第 28 页 共 29页2 课程设计原理2.1 课设题目粗略分析根据课设题目要求，拟将整体程序分为两大模块。以下是两个模块的大体分析：
3、1. 创建网图并确定网图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用邻接表和邻接矩阵（起点、终点和权值）两种存储结构，方便以后的编程。2.Prim算法。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树边的权值的集合。其思想是：令集合U的初值为Uu0（即假设构造最小生成树时从结点u0开始），集合T的初值为T=。从所有结点u属于U和结点v属于V但不属于U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断重复，当U=V时，最小生成树便构造完毕。2.2 原理图介绍2
4、.2.1 功能模块图显示菜单进行选择选择创建（有）无向图及存储方式有向图邻接矩阵无向图邻接矩阵有向图邻接表无向图邻接表调用普里姆算法输出最小生成树结束开始图2.1 功能模块图 2.2.2 流程图分析1. 主函数开始显示菜单，选择输入1或2选择1选择2 调用createAgraph()函数结束选择1调用CreateGraph()函数选择2调用CreateMGraph()函数调用createALgraph()函数调用Prim函数，输出最小生成树 图2.2 主函数流程图2. CreateMGraph()函数开始int i,j,kfor(i=0;in;i+)scanf(“n%c”,&(G-vexsi)
5、;for(i=0;in;i+)for(j=0;in;i+)i=jG-edgesij=0;YNG-edgesij=max;for (k=0;ke;k+)scanf(n%d,%d,%d,&i,&j,&weight);G-edgesij=weight;OutPut(G);prim(G-edges,G-n,G-vexs);结束 图2.3 CreateMGraph()函数流程图3Prim()函数开始int i,j,k,lowcost100,mincost;for(i=1;in;i+) lowcosti=gm0i;closevertexi=0; seti=0; i=1; j=1;YYlowcost0=0;
6、closevertex0=0;for(i=1;in;i+)mincost=max;j=1;k=1;jnlowcostjmincost&lowcostj!=0mincost=lowcostj;k=j;j+;NNprintf(顶点的序号=%d 边的权值=%dn,k,mincost); lowcostk=0; for(j=0;jn;j+)gmkjn),&(g-e);for(i=0;in;i+)scanf(%d,&(g-adjlisti.vertex);g-adjlisti.firstedges=NULL;for(k=0;ke;k+)scanf(%d,%d,%d,&i,&j,&w);s=(edgeno
7、de*)malloc(sizeof(edgenode);s-adjvex=j;s-weight=w;s-next=g-adjlisti.firstedges;g-adjlisti.firstedges=s;结束图2.5 createAgraph()函数流程图5. 邻接矩阵Output()输出函数开始int i,j;for (i=0;in;i+) printf(%d ,G-vexsi);for(i=0;in;i+)for(j=0;jn;j+)printf(t%d ,G-edgesij);结束图2.6 Output()函数流程图 3 数据结构分析3.1 存储结构定义邻接矩阵及邻接表的结构体（1）邻
8、接矩阵#define MaxVertexNum 100#define max 1000typedef int VertexType;typedef int EdgeType;typedef struct VertexType vexsMaxVertexNum; EdgeType edgesMaxVertexNumMaxVertexNum; int n,e; MGraph;（2）邻接表#define MaxVertexNum 100typedef int vertextype;typedef struct node int adjvex; int weight; struct node *nex
9、t; 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
10、,e; graph; /*邻接表转换成邻接矩阵辅助结构体*/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;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; /*初
11、始化邻接矩阵*/ printf(输入边对应的两个顶点的序号及权值：); for (k=0;ke;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);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+
