数据结构最小生成树普利姆算法.doc

. .
: .
-优选
. .
-优选
. .
一、问题分析和任务定义
在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的最小生成树。
问题的输入数据的格式为:首先提示输入带权网络的顶点边数,我定义的为整形数据型,然后输入每一条边的信息,即边的两个顶点以及权值,是十进制整数类型,这样我们就建立一个带权网络,并用邻接矩阵来存储,生成一个方阵显示出来。
问题的输出数据格式为:输出是以邻接矩阵存储构造下的方阵,以及从不同顶点开场省城的最小生成树。
题目要求以及到达目标:题目要求用普利姆算法实现任意给定的网和顶点的所有最小生成树,并且输出各边的权值。
-优选
. .
三、测试数据
第一组
顶点数〔vertices〕、边数〔edge〕:2、1
起始节点〔starting〕、下个节点〔terminal〕、权值〔weights〕:1、2、5 ,预测结果<1,2>5
第二组
顶点数〔vertices〕、边数〔edge〕:3、3
起始节点〔starting〕、下个节点〔terminal〕、权值〔weights〕:1、2、4
1、3、5
2、3、6
预测结果<1,2>4、<1,3>5
第三组
顶点数〔vertices〕、边数〔edge〕:4、5 ,
起始节点〔starting〕、下个节点〔terminal〕、权值〔weights〕:1、2、3
1、3、4
1、4、6
2、4、7
3、4、5
预测结果<1,2>3、<1,3>4、<1,4>6
-优选
. .
四、算法思想
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 <>
#include <>
#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++) /* n个顶点,n-1条边*/
{ lowcost[i]=g[1][i]; /* 初始化*/
closest[i]=1; /* 顶点未参加到最小生成树中*/
}
lowcost[1]=0; /* 标志顶点1参加U集合*/
for(i=2;i<=n;i++) /* 形成n-1条边的生成树*/
{
min=inf;
k=0;
for(j=2;j<=n;j++) /* 寻找满足边的一个顶点在U,另一个顶点在V的最小边*/