普里姆与克鲁斯卡尔算法.doc

前言
从学习《数据结构》这门课程开始,我已发现了学习算法的乐趣,在学习这门课的过程中也学到了许多计算机应用基础知识,对计算机的机体也有了一个初步的了解,又在课余时间阅读了大量有关算法设计与分析的图书,在此基础上,利用贪心算法,编写了一个用prim和kruskal算法求解最小生成树,也以此检验自己一学期所学成果,加深对算法设计与分析这门课程的理解,由于所学知识有限,难免有些繁琐和不完善之处,下面向大家介绍此程序的设计原理,方法,内容及设计的结果。
本程序是在windows 环境下利用Microsoft Visual C++ ,主要利用贪心算法的思想,以及数组,for语句的循环,if语句的嵌套,运用以上所学知识编写出的prim和kruskal算法求解最小生成树,在输入其边的起始位置,种植位置以及权值后,便可分别输出此网的prim和kruskal算法最小生成树的边的起始位置,终止位置以及权值。
正文
设计方法和内容
:Microsoft Visual C++
:
所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法的基本思路如下:
。
。
,得到子问题的局部最优解。
。

(普里姆)算法思想
无向网的最小生成树问题
此算法的思想是基于点的贪心,力求从源点到下一个点的距离最短,以此来构建临接矩阵,所以此算法的核心思想是求得源点到下一个点的最短距离,下面具体解释如何求此最短距离:
在图中任取一个顶点k作为开始点,令集合U={k},集合w=V-U,其中v为图中所有顶点的集合,然后找出:一个顶点在集合U中,另一个顶点在集合W中的所有边中,权值最短的一条边,,并将该边顶点全部加入集合U中,并从W中删去这些顶点,然后重新调整
U中顶点到W中顶点的距离,使之保持最小,在重复此过程,直到W为空集为止,求解过程如下:
由图可知最小生成树的步骤,假设开始顶点就选为1,故首先有u={1},w={2,3,4,5}。
(克鲁斯卡尔)算法的基本思想
kruskal(克鲁斯卡尔)算法的基本思想是:将无向图的所有边按权值递增顺序排列,依次选定权值数较小的边,但要求后面选取的边不能与前面选区的边构成回路,若构成回路,则放弃该条边,然后再选后面权值较大的边,n个顶点的图中,选取n-1条边即可。
注意:kruskal算法的贪心是从源点到下一个点的距离最短。
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出发求最小生成的数边,[i].fromvex=1。[i].endvex=i+1,[i].weight=[1][i+1],再利用第二个for循环找到权值最小的树边,从顶点为2开始循环,当j=k-1且小于网中总顶点数时,权值小于无穷则将此权值付给min,并令边m=j。
(5)重新修改树边的距离,将原来的边用权值小的边替换,若当前边k小于n(原定边数),则令 tl=[i].endvex,w=[j][tl],若w<[i].weight,则令 [i].weight=w,[i].fromvex=j。
(6)最后利用for循环键入每条边的起始点,终结点及边上的权值。

:
(1)定义网中的顶点数,网的边数,这里将网的顶点数定为6个,网的