大数据结构最小生成树普利姆算法.docx
《大数据结构最小生成树普利姆算法.docx》由会员分享，可在线阅读，更多相关《大数据结构最小生成树普利姆算法.docx（21页珍藏版）》请在冰点文库上搜索。
大数据结构最小生成树普利姆算法
一、问题分析和任务定义
在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
#defineinf9999
#definemax40
#definelinelenght77
（2）普里姆算法
voidprim（intg[][max],intn）/*prim的函数*/
{
intlowcost[max],closest[max];
inti,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的最小边*/
if（（lowcost[j]=0））
{
min=lowcost[j];
k=j;
}
printf（"（%d,%d）%d\t",closest[k],k,min）;
lowcost[k]=0;/*顶点k加入U*/
for（j=2;j<=n;j++）/*修改由顶点k到其他顶点边的权值*/
if（g[k][j]{
lowcost[j]=g[k][j];
closest[j]=k;
}
printf（"\n"）;
}
}
（3）输出分割线
intpriline（inth）/*输出一条分割线*/
{
intg;
printf（"\n|"）;
for（g=0;gprintf（"*"）;
printf（"|\n"）;
}
（4）提示错误信息
interror（）/*提示错误信息*/
{
printf（"\n\n|************************E*R*R*O*R************************|\n"）;
printf（"InputerrorsorDataoverflow!
!
!
pleasere-enter\n\n"）;
fflush（stdin）;/*清除缓存*/
}
（5）建立无向图
intadjg（intg[][max]）/*建立无向图*/
{
intn,e,i,j,k,v1=0,v2=0,weight=0;
printf（"Inputthenumberofvertices,numberoftheedge:
"）;
scanf（"%d,%d",&n,&e）;
while（e<=0||e>=n*（n-1）||n>=max）
{
error（）;
printf（"Inputthenumberofvertices,numberoftheedge:
"）;
scanf（"%d,%d",&n,&e）;
}
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
g[i][j]=inf;/*初始化矩阵，全部元素设为无穷大*/
for（k=1;k<=e;k++）
{
printf（"Inputthe%dontheedgeofthestartingpoint,terminal,weights:
",k）;
scanf（"%d,%d,%d",&v1,&v2,&weight）;
while（v1==v2||v1>n||v2>n||v1<1||v2<1）
{
error（）;
printf（"Inputthe%dontheedgeofthestartingpoint,terminal,weights:
",k）;
scanf（"%d,%d,%d",&v1,&v2,&weight）;
}
g[v1][v2]=weight;
g[v2][v1]=weight;
}
return（n）;
}/*返回节点个数n*/
（6）输出无向图的邻接矩阵
voidpri（intg[][max],intn）/*输出无向图的邻接矩阵*/
{
inti,j;
for（i=0;i<=n;i++）
printf（"%d\t",i）;
for（i=1;i<=n;i++）
{
printf（"\n%d\t",i）;
for（j=1;j<=n;j++）/*输出边的权值*/
{
if（g[i][j]==inf）printf（"%c\t",'\354'）;
elseprintf（"%d\t",g[i][j]）;
}
}
printf（"\n"）;
}
（7）主函数模块
voidmain（）/*主函数*/
{
intg[max][max],n;priline（linelenght）;
n=adjg（g）;priline（linelenght）;priline（linelenght）;
printf（"Inputtheadjacencymatrixwithoutdirectedgraph:
\n"）;
pri（g,n）;
printf（"\n"）;
printf（"Minimumspanningtreestructure:
\n"）;
prim（g,n）;
getch（）;
}
六、算法设计与分析
（1）关于带权网络的存储形式
要实现对于任意给定带权网络和顶点，运用PRIM基本算法思想求解所有的最小生成树的运算。
在这里我们首先要明确所选用的数据结构，即选用何种数据结构存储来存储带权网络，这是必选首先解决的问题，所以我们选择了图的邻接矩阵存储方式来存储带权网络，建图时采用邻接矩阵的结构，定义邻接矩阵用到了一维数组和二维数组，分别存储顶点信息和边的权值。
由于该算法对图中的边的权值频繁比较，所以采用邻接矩阵比较方便，并在此基础上实现带权网络的建立以及输出显示。
（2）关于普利姆算法的基本思想
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的最小生成树。
对于最小生成树问题
最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。
（3）概要设计
通过邻接矩阵的建立，可以将任意两点的权值存入其中，便于进行各边的权值的比较修改，在普利姆算法中，为实现这个算法需附设一个辅助数组closedge，以记录从U到V-U具有最小代价的边，对每个顶点vi∈V-U,在辅助数组中存在一个相应分量closedge[i-1]，他包括两个域，其中lowcost存储该边上的权值。
显然，
closedge[i-1].lowcost=Min{cost（u,vi）|u∈U}
从算法可以看出每加入一个顶点到U中，closedge数组都会发生相应的变化。
程序模块之间的调用：
在主函数中调用邻接矩阵的初始化函数，邻接矩阵的生成函数，PRIM算法的函数，图的构造函数，输出函数。
邻接矩阵的生成函数主要解决的是边的信息存储问题，而PRIM算法的函数是解决计算出最小生成树的功能。
详细设计和编码
首先我在接下来给出总的流程：
结果分析：
本课程设计的要求
对于任意给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树并输出这些边的权值，所以如何实现输出显示所有的最小生成树关键问题所在，经过分析调试，用一个for语句就可以解决这个问题，从每个顶点出发，开始每一次遍历并输出显示出来。
算法的时间和空间性能分析
根据程序中算法的循环语句可以判断出普利姆算法的时间复杂度为O（n2）算法和图中的边数无关。
因此普利姆算法适合求稠密网的最小生成树，因为在算法中用邻接矩阵的存储结构，在无向图中，邻接矩阵是对称的。
所以仅需要存储上三角或下三角的元素，因此需要n（n+1）的存储空间。
测试结果
界面的截图
输入的情况的截图
输出结果的截图
输入错误的截图
七、源程序
源程序代码（有注释详解）
#include
#include
#defineinf9999
#definemax40
#definelinelenght77
voidprim（intg[][max],intn）/*prim的函数*/
{
intlowcost[max],closest[max];
inti,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的最小边*/
if（（lowcost[j]=0））
{
min=lowcost[j];
k=j;
}
printf（"（%d,%d）%d\t",closest[k],k,min）;
lowcost[k]=0;/*顶点k加入U*/
for（j=2;j<=n;j++）/*修改由顶点k到其他顶点边的权值*/
if（g[k][j]{
lowcost[j]=g[k][j];
closest[j]=k;
}
printf（"\n"）;
}
}
intpriline（inth）/*输出一条分割线*/
{
intg;
printf（"\n|"）;
for（g=0;gprintf（"*"）;
printf（"|\n"）;
}
interror（）/*提示错误信息*/
{
printf（"\n\n|************************E*R*R*O*R************************|\n"）;
printf（"InputerrorsorDataoverflow!
!
!
pleasere-enter\n\n"）;
fflush（stdin）;/*清除缓存*/
}
intadjg（intg[][max]）/*建立无向图*/
{
intn,e,i,j,k,v1=0,v2=0,weight=0;
printf（"Inputthenumberofvertices,numberoftheedge:
"）;
scanf（"%d,%d",&n,&e）;
while（e<=0||e>=n*（n-1）||n>=max）
{
error（）;
printf（"Inputthenumberofvertices,numberoftheedge:
"）;
scanf（"%d,%d",&n,&e）;
}
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
g[i][j]=inf;/*初始化矩阵，全部元素设为无穷大*/
for（k=1;k<=e;k++）
{
printf（"Inputthe%dontheedgeofthestartingpoint,terminal,weights:
",k）;
scanf（"%d,%d,%d",&v1,&v2,&weight）;
while（v1==v2||v1>n||v2>n||v1<1||v2<1）
{
error（）;
printf（"Inputthe%dontheedgeofthestartingpoint,terminal,weights:
",k）;
scanf（"%d,%d,%d",&v1,&v2,&weight）;
}
g[v1][v2]=weight;
g[v2][v1]=weight;
}
return（n）;
}/*返回节点个数n*/
voidpri（intg[][max],intn）/*输出无向图的邻接矩阵*/
{
inti,j;
for（i=0;i<=n;i++）
printf（"%d\t",i）;
for（i=1;i<=n;i++）
{
printf（"\n%d\t",i）;
for（j=1;j<=n;j++）/*输出边的权值*/
{
if（g[i][j]==inf）printf（"%c\t",'\354'）;
elseprintf（"%d\t",g[i][j]）;
}
}
printf（"\n"）;
}
voidmain（）/*主函数*/
{
intg[max][max],n;priline（linelenght）;
n=adjg（g）;priline（linelenght）;priline（linelenght）;
printf（"Inputtheadjacencymatrixwithoutdirectedgraph:
\n"）;
pri（g,n）;
printf（"\n"）;
printf（"Minimumspanningtreestructure:
\n"）;
prim（g,n）;
getch（）;
}
八、测试数据
第一组
第二组
第三组
九、课程设计项目进度表及任务分配表及任务分配表
进度
日期
进度
2011-1-15
搜集资料
2011-1-16至17
设计算法
2011-1-18
将问题分块，然后分块写出程序
2011-1-19
将每块程序衔接好，进行调试
2011-1-20
对程序进行最后修改，整理实验报告
分配表
成员
座号
项目内容
序号
蒋家权
15号
编写程序调试程序
01
陈相财
25号
编写程序调试程序
02
吴继伟
6号
收集资料调试程序
03
梁丽春
7号
收集资料调试程序
04
十、设计心得
我们设计的题目是最小生成树的构造，在这次实践中遇到了各种问题，碰到问题有时总是百思不得其解
最开始，程序要求输入数值时，如果任意没有按照程序给定的类型输入，程序就会出现死循环，虽然加入了检测程序段，但是当我们不按个数输入的时候程序也出现了不稳定，又进入死循环了。
我们想了很多办法，其中之一就是加入break这个函数。
不过，并没有出项我们想要的结果，导致循环检测输入的函数while无法继续执行，中途就中断了。
有点大失所望，但是我们没有气馁。
记得以前老是又用过清空缓存这个函数，会不会失这个原因呢？
interror（）/*提示错误信息*/
{
printf（"\n\n|************************E*R*R*O*R************************|\n"）;
printf（"InputerrorsorDataoverflow!
!
!
pleasere-enter\n\n"）;
fflush（stdin）;/*清除缓存*/
}
经过我们反复测试，最终确定原因，正是出在这里，导致数据无法更新。
最小生成树主要由PRIM算法完成，由于老师平时课上对普利姆算法的知识的透彻讲解，通过整体构思，，于是，我们先确立了基本步骤：
1.建立一个具有n个定点的无向图2.接着创建一个邻接矩阵来存储该图，然后初始化该矩阵，最后根据普利姆算法，得到了最小生成树以及各边的权值；好的开头是成功的一半，按照这个步骤，我们忙碌了3天，在大家的共同努力下，我们总算将此程序设计出来。
尽管不是自己独立完成，但仍然很欣慰，因为在设计的过程中，让我们了解到要设计一个大型程序，查找资料是至关重要的，在他人的基础上，再根据自己所学进行修改与调试，最后设计出自己想要的程序，这过程艰辛，但只要你持之以恒，定可将问题解决。
通过本次实验巩固了课本的基本知识，熟练运用课程知识。
提高我们组织数据及编写程序的能力，使我们能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的问题在计算机内部表示出来并用软件解决问题，本次实验大大提高了对编程的爱好，发现，只要认认真真的去思考，没有办不到的事情，程序设计过程有
十、参考书目
参考目录书
（1）王昆仑，李红。
数据结果算法：
c语言版。
中国铁道出版社，2007
（2）严蔚敏，吴伟明。
数据结构：
c语言版。
清华大学出版社，2002
（3）徐孝凯，数据结构实用教程，清华大学出版社。
2004
（4）耿国华，数据结构，c语言描述，西安电子科技大学出版社。
2004
学校地址：
福建省武夷山市武夷大道16号
设计单位：
数学与计算机系
版本号：
WyuKcsjVer2007
升级会员 