请输入您要查询的百科知识:

 

词条 Prim
释义

最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图中选择n-1条边并使这个图仍然连通(也即得到了一棵生成树),同时还要考虑使树的权最小。 为了得到最小生成树,人们设计了很多算法,最著名的有prim算法和kruskal算法。教材中介绍了prim算法,但是讲得不够详细,理解起来比较困难,为了帮助大家更好的理解这一算法,本文对书中的内容作了进一步的细化,希望能对大家有所帮助。

举例

假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:

1:初始化:U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。

2:在所有u∈U,v∈V-U的边(u,v)∈E中,找一条权最小的边(u 0,v 0),将此边加进集合TE中,并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V-U中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。

3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n-1次(设n为图中顶点的数目),TE中也增加了n-1条边,这n-1条边就是需要求出的最小生成树的边。

具体算法

规定

了解了prim算法的基本思想以后,下面我们就可以看看具体的算法。

为了和教材保持一致,我们仍然规定:连通网用邻接矩阵net表示,若两个顶点之间不存在边,其权值为计算机内允许最大值,否则为对应边上的权值。

首先定义数据类型

type adjmatrix=array [1..n,1..n] of real; //定义一个n*n的矩阵类型adjmatrix,以便存储邻接矩阵//

edge=record

beg,en:1..n;

length:real;

end; //定义边的存储结构为edge,其中beg是边的起点, en 是边的终点,length是边的权值//

treetype=array [1..n-1] of edge; //定义一个基类型为edge的数组类型

var net:adjmatrix; //定义一个adjmatrix类型的变量net,图的邻接矩阵就存放在net中//

tree:treetype; //定义一个treetype类型的变量tree,tree中可以存放n-1条边的信息,包括起点、终点及权值。在算法结束后,最小生成树的n-1 条边就存放在tree中//

算法如下(设n为构造的出发点)

procedure prim(net:adjmatrix;var tree:treetype);

//过程首部.参数的含义是:值参数net传递图的邻接矩阵,变参tree指明最小生成树的存放地址//

begin

for v:=1 to n-1 do //此循环将顶点n与图中其它n-1个顶点形成的n-1条边存放在变量tree中//

[ tree[v].beg:=n;

tree[v].en:=v;

tree[v].length:=net[n,v] ]

for k:=1 to n-1 do

//此循环执行算法思想中的步骤2,循环体每执行一次,TE中将增加一条边,在算法中,这条增加的边存放在变量tree中的第k个元素上,可以这样认为,tree中从第1到第k号元素中存放了TE和U的信息。注意:在算法思想中我们特别提醒了TE和U的动态性,表现在算法中,这种动态性 体现在循环变量k的变化上。//

[ min:=tree[k].length;

for j:=k to n-1 do

if tree[j].length<min then

[min:=tree[j].length;

m:=j; ] //上面两条语句用于搜索权值最小的边//

v:=tree[m].en; //此语句记录刚加入TE中的边的终点,也即即将加入U中的顶点//

edge:=tree[m];

tree[m]:=tree[k];

tree[k]:=edge; //上面三句用于将刚找到的边存储到变量tree的第k号元素上//

for j:=k+1 to n-1 do

//此循环用于更新tree中第k+1到第n-1号元素。更新以后这些元素中的en子项是各不相同的,它们的全部就是集合V-U;beg子项则可以相同,但它们需满足两个条件:一是应属于集合U;另一是beg子项和en子项行成的边,在所有与顶点en联系的边中权值应最小。//

[ d:=net[v.tree[j].en];

if d<tree[j].length

then [tree[j].length:=d;

tree[j].beg:=v;]

]

]

for j:=1 to n-1 do //此循环用于输出最小生成树//

writeln(tree[j].beg,tree[j].en,tree[j].length);

end;

评价

此算法的精妙之处在于对求权值最小的边这一问题的分解(也正是由于这种分解,而导致了算法理解上的困难)。按照常规的思路,这一问题应该这样解决:分别从集合V-U和U中取一顶点,从邻接矩阵中找到这两个顶点行成的边的权值,设V-U中有m个顶点,U中有n个顶点,则需要找到m*n个权值,在这m*n个权值中,再查找权最小的边。循环每执行一次,这一过程都应重复一次,相对来说计算量比较大。而本算法则利用了变量tree中第k+1到第n-1号元素来存放到上一循环为止的一些比较结果,如以第k+1号元素为例,其存放的是集合U中某一顶点到顶点tree.en的边,这条边是到该点的所有边中权值最小的边,所以,求权最小的边这一问题,通过比较第k+1号到第n-1号元素的权的大小就可以解决,每次循环只用比较n-k-2次即可,从而大大减小了计算量。

完全代码

program prim;

const map:array [1..6,1..6] of integer=((0,6,1,5,0,0),

(6,0,5,0,3,0),

(1,5,0,5,6,4),

(5,0,5,0,0,2),

(0,3,6,0,0,6),

(0,0,4,2,6,0));//样例输入

var

i,j,l:integer;

min,minn:longint;

f,d:array [1..6] of integer;

s:array [1..6,1..3] of integer;

v,p:set of 1..6;

begin

l:=1;

p:=[ ];

v:=[ ];

for i:=2 to 6 do v:=v+[i];

p:=p+[1];

for i:=1 to 6 do f[i]:=1000;//还可以写成 filldword(f,sizeof(f) div 2,1000)

f[1]:=0

for i:=1 to 6 do d[i]:=0;;//还可以写成 fillchar(d,sizeof(d),0);

s[1,3]:=0;

for i:=1 to 5 do

begin

min:=1000;

for j:=1 to 6 do

begin

if (f[j]>map[l,j]) and (j in v) and (map[l,j]<>0) then

begin f[j]:=map[l,j];d[j]:=l;end;

if (f[j]<min) and (f[j]>0) then begin min:=f[j];minn:=j; end;

writeln(d[j]);

end;

f[minn]:=0;

v:=v-[minn];

p:=p+[minn];

s[i,1]:=d[minn];

l:=minn;

s[i,2]:=minn;

s[i,3]:=min;

end;

for i:=1 to 5 do write(s[i,1],'to',s[i,2],'=',s[i,3],' --> ');

readln;

end.

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/2/12 6:42:36