普里姆和克鲁斯卡尔算法Word格式.doc
《普里姆和克鲁斯卡尔算法Word格式.doc》由会员分享，可在线阅读，更多相关《普里姆和克鲁斯卡尔算法Word格式.doc（13页珍藏版）》请在冰点文库上搜索。
prim算法的贪心是任意点到生成树的距离最短，也就是边的最小。
三，设计方法与内容：
1.Prim（普里姆）算法：
假设网用邻接矩阵作存储结构，与图的邻接矩阵类似，只是将0变为无穷，1变为对应边上权值，而矩阵中对角线上的元素为0。
（1）定义网中的顶点数，网的边数，这里将网的顶点数定为6个，网的边数定为10个。
（2）定义一个名为edgeset类，其数据成员fromvex,endvex,weight,分别为一条边的起点，终点和权值。
（3）定义一个名为tree的类，定义了一个最小生成树边集的数组，用数组记录具有最小代价的边，找到后，将该边作为最小生成树的树边保存起来，再定义一个普里姆算法的成员函数prim（tree&
t）。
（4）对prim（tree&
t）函数进行类外定义，分别将顶点数定义为k,边为m,权值为w,定义一个变量min，使其等于32767，即无穷大，利用for循环从顶点1出发求最小生成的数边，即设t.ct[i].fromvex=1。
令终止点t.ct[i].endvex=i+1,令t.ct[i].weight=t.s[1][i+1],再利用第二个for循环找到权值最小的树边，从顶点为2开始循环，当j=k-1且小于网中总顶点数时，权值小于无穷则将此权值付给min,并令边m=j。
（5）重新修改树边的距离，将原来的边用权值小的边替换，若当前边k小于n（原定边数），则令tl=t.ct[i].endvex，w=t.s[j][tl]，若w<
t.ct[i].weight，则令t.ct[i].weight=w，t.ct[i].fromvex=j。
（6）最后利用for循环键入每条边的起始点，终结点及边上的权值。
2.kruskal算法：
（2）定义一个名为edgeset2的类，其数据成员fromvex,endvex,weight,分别为一条边的起点，终点和权值。
（3）定义一个名为tree2的类，定义了一个最小生成树边集的数组，用edgesetge2[e+1]存放网中所有的边，定义一个s2[n+1][n+1]，s为一个集合，一行元素s[i][0]~s[i][n]表示一个集合，若s[i][t]=1。
则表示顶点t属于该集合，否则不属于该集合，再定义一个普里姆算法的成员函数kruskal（tree2&
t2）。
（4）对kruskal（tree2&
t2）函数进行类外定义,定义k并设初值为1用来统计生成树的边数，定义d并设初值为1用来表示待扫描边的下标位置，定义两个变量m1,m2用来记录一条边的两个顶点所在集合的序号，如果t2.ge2[d].fromvex==j且t2.s2[i][j]==1，则令m1=i，若t2.ge2[d].endvex==j且t2.s2[i][j]==1则令m2=i，最后判断m1是否等于m2，若不等于则令t2.c2[k]=t2.ge2[d]，k自加，求出一条边后，合并两个集合，另一个集合设置为空。
（6）最后利用for循环键入每条边的起始点，终结点及边上的权值，要求输入的网中的边上的权值必须为从大到小排列，调用kruskal（t）循环输出一条边的起始点，终结点及边上的权值。
2.3设计流程图
定义数据成员fromvex,endvex,weight,分别为一条边的起点，终点和权值。
定义网中的顶点数n=6，网的边数e=10
从顶点1出发求最小生成树的边
先找权值最小的树边,然后重新修改树边的距离,原来的边用权值较小的边取代
最后利用for循环键入每条边的起始点，终结点及边上的权值
Prim算法
Kruskal算法
定义了一个最小生成树边集的数组，用edgesetge2[e+1]存放网中所有的边
定义一个s2[n+1][n+1]，s为一个集合，一行元素s[i][0]~s[i][n]表示一个集合，若s[i][t]=1。
则表示顶点t属于该集合，否则不属于该集合
定义k并设初值为1用来统计生成树的边数，定义d并设初值为1用来表示待扫描边的下标位置，定义两个变量m1,m2用来记录一条边的两个顶点所在集合的序号
图2-2
2.4设计结论
Prim算法：
在图中任取一个顶点k作为开始点，令集合U={ k},集合w=V-U,其中v为图中所有顶点的集合，然后找出：
一个顶点在集合U中，另一个顶点在集合W中的所有边中，权值最短的一条边，，并将该边顶点全部加入集合U中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，在重复此过程，直到W为空集为止
Kruskal算法：
其中两个算法的贪心思想有本质的区别：
而prim算法的贪心是任意点到生成树的距离最短，也就是边的最小。
有关说明
（1）程序运行刚开始会出现一个界面：
*************请选择一种算法*****************
1.prim算法求解最小生成树
2.kruskal算法求解最小生成树
此时便可输入用户想要选择的数值，回车然后进入如（图一或图二）的界面。
（2）接着根据提示输输入一条边的起始点，终结点及边上的权值，如（图三）界面。
（3）重复步骤
（2）十次。
（5）即可显示此算法下的最小生成树。
如（图四）界面。
致谢
这次课程设计实训老师给我了很大的帮助，让我发现了自身的不足之处，在实际操作过程中犯的一些错误，同时还有有意外的收获。
在具体操作中对这学期所学的数据结构的理论知识得到巩固，达到实训的基本目的，同时也认识到在以后的上机中应更加注意自己曾犯的错误，也发现上机实训的重要作用，特别是对数组和邻接矩阵有了深刻的理解。
通过实际操作，学会数据结构程序编程的基本步骤、基本方法，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。
在此感谢学院领导，老师们给我们提供了这样一个良好的平台，让我们学有所用，把我们所学的理论知识与实践结合，锻炼了自己动手操作的能力，希望自己以后有机会多进行这样的实训，培养自身独立思考问题的能力，提高实际操作水平。
参考文献
[1]李根强《C++数据结构》2005年1月第一版中国水利水电出版社
[2]侯识忠《数据结构算法程序集》
[3][018602-01/tp]谭浩强《C程序设计》2005年7月第三版清华大学出版社1-378页。
[4]顾仁《高级C++语言程序设计技巧与实例》1995年11月第一版机械工业出版社1-462页
[5]陈明《数据结构（C++版）》2005年3月第一版清华大学出版社
[6][020923-01/tp]谭浩强《C++面向对象程序设计》2006年1月第一版清华大学出版社1-288页
[7]王晓东《数据结构C++语言》2005年7月第一版清华大学出版社
附录：
//*************prim算法*********************
#include<
iostream.h>
constintn=6;
//网中顶点数
constinte=10;
//网中边数
classedgeset//定义一条生成树的边的类
{public:
intfromvex;
//边的起点
intendvex;
//边的终点
intweight;
//边的权值
};
classtree
ints[n+1][n+1];
//网的邻接矩阵
edgesetct[n+1];
//最小生成树的边集
voidprim（tree&
t）;
//普里姆算法
voidtree:
:
prim（tree&
t）
{
inti,j,k,min,tl,m,w;
//k为当前顶点数,m为当前边数,w为当前权值
for（i=1;
i<
n;
i++）//从顶点1出发求最小生成树的边
{t.ct[i].fromvex=1;
t.ct[i].endvex=i+1;
t.ct[i].weight=t.s[1][i+1];
}
for（k=2;
k<
=n;
k++）
{min=32767;
m=k-1;
for（j=k-1;
j<
j++）//找权值最小的树边
if（t.ct[j].weight<
min）
{min=t.ct[j].weight;
m=j;
}
edgesettemp=t.ct[k-1];
t.ct[k-1]=t.ct[m];
t.ct[m]=temp;
j=t.ct[k-1].endvex;
for（i=k;
i++）//重新修改树边的距离
{tl=t.ct[i].endvex;
w=t.s[j][tl];
if（w<
t.ct[i].weight）//原来的边用权值较小的边取代
{t.ct[i].weight=w;
t.ct[i].fromvex=j;
}
}
}
}
//************kruskal算法******************
classedgeset2
classtree2//定义生成树
edgesetc2[n];
//存放生成树的边
edgesetge2[e+1];
//存放网中所有边
ints2[n+1][n+1];
//s为一个集合，一行元素s[i][0]~s[i][n]表示一个集合
//若s[i][t]=1。
则表示顶点t属于该集合，否则不属于
voidkruska（tree2&
t2）;
voidtree2:
kruska（tree2&
t2）
{inti,j;
for（i=1;
i++）
for（j=1;
j++）
if（i==j）t2.s2[i][j]=1;
elset2.s2[i][j]=0;
intk=1;
//统计生成树的边数
intd=1;
//表示待扫描边的下标位置
intm1,m2;
//记录一条边的两个顶点所在集合的序号
while（k<
n）
{for（i=1;
for（j=1;
{if（（t2.ge2[d].fromvex==j）&
&
（t2.s2[i][j]==1））
m1=i;
if（（t2.ge2[d].endvex==j）&
m2=i;
}
if（m1!
=m2）
{t2.c2[k]=t2.ge2[d];
k++;
{t2.s2[m1][j]=t2.s2[m1][j]||t2.s2[m2][j];
//求出一条边后，合并两个集合
t2.s2[m2][j]=0;
//另一个集合设置为空
}}
d++;
voidmain（）
{intz;
for（z=1;
z<
=3;
z++）
{cout<
<
"
*************请选择一种算法*****************"
endl;
cout<
1.prim算法求解最小生成树"
2.kruskal算法求解最小生成树"
cin>
>
z;
if（z==1）
{intj,w;
treet;
cout<
——prim算法求最小生成树——"
请连续输入网的10条边"
for（inti=1;
for（intj=1;
if（i==j）t.s[i][j]=0;
elset.s[i][j]=32767;
//若（i,j）边上无权值，用32767来代替无穷
for（intk=1;
=e;
k++）//建立网的邻接矩阵
{
cout<
请输入一条边的起始点，终结点及边上的权值：
;
cin>
i>
j>
w;
t.s[i][j]=w;
t.s[j][i]=w;
}
t.prim（t）;
//用普里姆算法求最小生成树
此算法构造出的最小生成树的起始边，终止边以及权值如下:
for（i=1;
i++）//输出n-1条生成树的边
t.ct[i].fromvex<
"
cout<
t.ct[i].endvex<
t.ct[i].weight<
else
{//kruskal
tree2t2;
——kruskal算法求最小生成树——"
请连续输入网的10条边（按权值从小到大的顺序）"
for（inti=1;
i++）
{
cout<
输入一条边的起始边，终止边以及权值:
"
cin>
t2.ge2[i].fromvex>
t2.ge2[i].endvex>
t2.ge2[i].weight;
}
t2.kruska（t2）;
for（i=1;
t2.c2[i].fromvex<
t2.c2[i].endvex<
t2.c2[i].weight<
（图一）
（图二）
（图四）
（图五）
第13页共13页
升级会员 