数据结构（C言语版本）课程设计报告_最小生成树的应用
武 夷 学 院 课程设计报告课程名称：数据结构C言语版本设计题目：最小生成树的应用学生班级：10计科1班学生姓名：指导教师：完成日期：2012-01-05 课程设计工程研究报告目录一、问题描述及根本要求1 -二、 实现本程序需要解决的问题如下1 -三、 测试数据2 -四、 算法思想3 -五、 模块划分4 -六、 算法设计与分析7 -七、 源程序11 -八、 测试数据14 -九、 课程设计工程进度表及任务分配表及任务分配表15 -十、 设计心得16 -十一 参考文献17 -一、为题描述及根本要求在n个城市间建立通信网络，需架设n-1条线路。求解如何以最低经济代价建设此通信网，这是一个最小生成树问题。要求：1利用普利姆算法求网的最小生成树；2输出生成树中各边及权值。 二、实现本程序需要解决的问题如下(1)、如何选择存储结构去建立一个带权网络。(2)、如何在所选存储结构下输出这个带权网络。(3)、如何实现prim算法的功能。(4)、如何从每个顶点开始找到所有的最小生成树的顶点。(5)、如何输出最小生成树的边及其权值。此问题的关键在于如何实现prim算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了屡次调试。首先我们对问题进行大致的概要分析：这个问题主要牵涉到通过prim的根本算法思想实现程序所要求的功能，该算法的主要思想是：假设N=V，E是连通网，TE是N上最小生成树中边的集合。算法从U=u0( u0V),TE=开始，重复执行下述操作：在所有uU,vV-U的边u,vE中找一条代价最小的边u0,v0并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，那么T=V，E为N的最小生成树。问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立一个带权网络，并用邻接矩阵来存储，生成一个方阵显示出来。问题的输出数据格式为：输出是以邻接矩阵形式输出，以及从不同顶点开始生成的最小生成树。题目要求以及到达目标：题目要求用prim算法实现给定无向网中边e和顶点n实现生成的最小生成树，输出生成树中的各边及权值。三、测试数据第一组顶点数vertices、边数edge：4、5起始节点starting、下个节点terminal、权值weights：1,2,11,3,22,4,53,4,41,4,6预测结果<1,2>1、<1,3>2、<3,4>4第二组顶点数vertices、边数edge：6，10，起始节点starting、下个节点terminal、权值weights：1,2,61,3,11,4,52,3,52,5,33,5,63,4,53,6,44,6,25,6,6预测结果<1,3>1、<3,6>4、<6,4>2、<3,2>5、<2,5>3 四、算法思想普里姆算法的根本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。 从连通网络 N = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点参加到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边参加到生成树的边集TE中，把它的顶点参加到集合U中。如此重复执行，直到网络中的所有顶点都参加到生成树顶点集合U中为止。假设N=(V，E)是一个连通网，TE是N上最小生成树中边的集合。那么构造N的最小生成树的步骤如下： 1初始状态，TE为，U=u0，u0V； 2在所有uU，vV-U的边(u，v) E中找一条代价最小的边(u，v)并入TE，同时将v并入U；重复执行步骤2n-1次，直到U=V为止。 在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。 对于每一个顶点vV-U，closestv为U中距离v最近的一个邻接点，即边 (v，closestv) 是在所有与顶点v相邻、且其另一顶点jU的边中具有最小权值的边，其最小权值为lowcostv，即lowcostv=costvclosestv，采用邻接表作为存储结构：设置一个辅助数组： lowcost域 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；closest域 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。用prim算法构造最小生成树的过程： 五、模块划分1预处理#include <stdio.h>#include <graphics.h>#define inf 9999#define max 40#define linelenght 772建立无向图int adjg(int gmax) /* 建立无向图 */ int n,e,i,j,k,v1=0,v2=0,weight=0; printf("Input the number of vertices, number of the edge:"); scanf("%d,%d",&n,&e); while(e<=0|e>0.5*n*(n-1)|n>=max) /*最大边数为，即0.5*n*(n-1)*/ error(); printf("Input the number of vertices, number of the edge:"); scanf("%d,%d",&n,&e); for(i=1;i<=n;i+) for(j=1;j<=n;j+) gij=inf; /* 初始化矩阵，全部元素设为无穷大 */ for(k=1;k<=e;k+) printf("Input the %d on the edge of the starting point, terminal, weights:",k); scanf("%d,%d,%d",&v1,&v2,&weight); while(v1=v2|v1>n|v2>n|v1<1|v2<1) error(); printf("Input the %d on the edge of the starting point, terminal, weights:",k); scanf("%d,%d,%d",&v1,&v2,&weight); gv1v2=weight; /* 无向网的邻接矩阵是对称矩阵 */ gv2v1=weight; return(n); /* 返回顶点个数n */3输出无向图的邻接矩阵void pri(int gmax,int n) /* 输出无向图的邻接矩阵 */ int i,j; for(i=0;i<=n;i+) printf("%dt",i); for(i=1;i<=n;i+) printf("n%dt",i); for(j=1;j<=n;j+) /* 输出边的权值 */ if(gij=inf) printf("%ct",'354'); else printf("%dt",gij); printf("n");void prim(int gmax,int n) /* prim函数 */ int lowcostmax,closestmax; int i,j,k,min; for(i=2;i<=n;i+) lowcosti=g1i; /* 初始化 */ closesti=1; lowcost1=0; /* 标志顶点1参加U集合 */ for(i=2;i<=n;i+) /* 形成n-1条边的生成树 */ min=inf; k=0; for(j=2;j<=n;j+) /* 寻找权值最小的一条边，并把权值赋给min */ if(lowcostj<min)&&(lowcostj!=0) min=lowcostj; k=j; printf("(%d,%d)%dt",closestk,k,min); lowcostk=0; /* 顶点k参加U */ for(j=2;j<=n;j+) /* 修改由顶点k到其他顶点边的权值 */ if(gkj<lowcostj) lowcostj=gkj; closestj=k; printf("n");
