数据结构（C言语版本）课程设计报告-最小生成树的应用.doc

武夷学院
课程设计报告
课程名称:
数据结构(C言语版本)
设计题目:
最小生成树的应用
学生班级:
学生姓名:
指导教师:
完成日期:
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}( 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的最小生成树。
问题的输入数据的格式为:首先提示输入带权网络的顶点边数,我定义的为整形数据型,然后输入每一条边的信息,即边的两个顶点以及权值,是十进制整数类型,这样我们就建立一个带权网络,并用邻接矩阵来存储,生成一个方阵显示出来。
问题的输出数据格式为:输出是以邻接矩阵形式输出,以及从不同顶点开始生成的最小生成树。
题目要求以及达到目标:题目要求用prim算法实现给定无向网中边e和顶点n实现生成的最小生成树,输出生成树中的各边及权值。
三、测试数据
第一组
顶点数(vertices)、边数(edge):4、5
起始节点(starting)、下个节点(terminal)、权值(weights):1,2,1
1,3,2
2,4,5
3,4,4
1,4,6
预测结果<1,2>1、<1,3>2、<3,4>4
第二组
顶点数(vertices)、边数(edge):6,10 ,
起始节点(starting)、下个节点(terminal)、权值(weights):1,2,6
1,3,1
1,4,5
2,3,5
2,5,3
3,5,6
3,4,5
3,6,4
4,6,2
5,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},u0∈V;
  (2)在所有u∈U,v∈V-U的边(u,v) ∈E中找一条代价最小的边(u′,v′)并入TE,同时将v′并入U;
重复执行步骤(2)n-1次,直到U=V为止。
 在普里姆算法中,为了便于在集合U和(V-U)之间选取权值最小的边,需要设置两个辅助数组closest和lowcost,分别用于存放顶点的序号和边的权值。
       对于每一个顶点v∈V-U,closest[v]为U中距离v最近的一个邻接点,即边(v,closest[v]) 是在所有与顶点v相邻、且其另一顶点j∈U的边中具有最小权值的边,其最小权值为lowcost[v],即lowcost[v]=cost[v][clos