数据结构课程设计报告(最小生成树完整版普利姆算法）..doc

武 夷 学 院 课程设计报告 课程伟 课程设计项目研究报告 目录 一、问题分析和任务定义 - 1 - 二、实现本程序需要解决的问题如下 - 1 - 三、测试数据 - 2 - 四、算法思想 - 3 - 五、模块划分 - 4 - 六、算法设计与分析 - 7 - 七、源程序 - 11 - 八、测试数据 - 14 - 九、课程设计项目进度表及任务分配表及任务分配表 - 16 - 十、设计心得 - 17 - 十、参考书目 - 18 - 一、问题分析和任务定义 在n个城市间建立通信网络，需架设n-1条线路。如何以最低经济代价建设此通信网，是一个最小生成树问题要求：（1）利用普利姆算法求网的最小生成树）输出生成树中各边及权值 二、实现本程序需要解决的问题如下 (1)、如何选择存储结构去建立一个带权网络。 (2)、如何在所选存储结构下输出这个带权网络。 (3)、如何实现PRIM算法的功能。 (4)、如何从每个顶点开始找到所有的最小生成树的顶点。 (5)、如何输出最小生成树的边及其权值。 此问题的关键在于如何实现PRIM算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。 首先我们对问题进行大致的概要分析： 这个问题主要牵涉到通过PRIM的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V),TE={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{E}）为N的最小生成树。 问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立一个带权网络，并用邻接矩阵来存储，生成一个方阵显示出来。 问题的输出数据格式为：输出是以邻接矩阵存储结构下的方阵，以及从不同顶点开始省城的最小生成树。 题目要求以及达到目标：题目要求用普利姆算法实现任意给定的网和顶点的所有最小生成树，并且输出各边的权值。 三、测试数据 第一组 顶点数（vertices）、边数（edge）：2、1 起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、5 ，预测结果1,25 第二组 顶点数（vertices）、边数（edge）：3、3 起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、4 1、3、5 2、3、6 预测结果1,24、1,35 第三组 顶点数（vertices）、边数（edge）：4、5 ， 起始节点（starting）、下个节点（terminal）、权值（weights）：1、2、3 1、3、4 1、4、6 2、4、7 3、4、5 预测结果1,23、1,34、1,46  四、算法思想 Prim算法求最小生成树的主要思想 此算法是普利姆与1957年提出的一种构造最小生成树的算法，主要思想是：假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V),TE={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{E}）为N的最小生成树。 对于最小生成树问题 最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。  五、模块划分 （1）预处理 #include stdio.h #include graphics.h #define inf 9999 #define max 40 #define linelenght 77 （2）普里姆算法 void prim(int g[][max],int n) /* prim的函数 */ { int lowcost[max],closest[max]; int i,j,k,min; for(i=2;i=n;i++)