数据结构15-最小生成树.ppt

该【数据结构15-最小生成树 】是由【3827483】上传分享，文档一共【26】页，该文档可以免费在线阅读，需要了解更多关于【数据结构15-最小生成树 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图的最小生成树
单击添加副标题
对于一张图进行深度优先搜索或宽度优先搜索，可生成一棵深度优先搜索树或宽度优先搜索树。搜索的出发点不同，生成树的形态亦不同。在一张有权连通图中，各边权和为最小的一棵生成树即为最小生成树。
计算最小生成树的思维方向：为了保证边权总和最小，必须保证
、添加(u,v)不能够形成回路、
、在保证１的前提下添加权尽可能小的，这样的边称之为安全边
有两种算法可计算图的最小生成树
、Kruskal算法
、Prim算法
①、Kruskal算法
找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。初始时，森林由单个结点组成的n棵树。
Const
maxn=200; maxe=maxn*maxn; /*顶点数和边数的上限*/
Type
edgetype=Record /*边的类型*/
x,y,c:longint; /*边权为c的边（x，y）*/
end;
Var
e:Array [1..maxe] of edgetype; /*边集，其中第i条边为(e[i].x,e[i].y)，该边的权为e[i].c*/
n,m,ans:longint; /*顶点数为n，边数为m*/
f:Array [1..maxn] of longint; /*并查集。其中f[i]为顶点i所在并查集的代表顶点，即子树根*/
Kruskal程序
通过函数top(i)计算顶点i所在子树的根
单击此处添加小标题
func top(i:longint):longint; /*计算和返回顶点i所在并查集的代表顶点*/
单击此处添加小标题
{ if i<>f[i] Then f[i]←top(f[i]); /*若i非所在并查集的代表顶点，则沿f[i]递归*/
单击此处添加小标题
top←f[i]; /*返回顶点i所在并查集的代表顶点*/
单击此处添加小标题
};/*top*/
单击此处添加大标题内容
通过过程Union(i,j,c)合并顶点i和顶点j所在的两棵树
现有边权为c的边（i，j）。若该边的两个端点分属于两棵树，顶点i和顶点j所在子树的根分别为x和v，则(i,j) 加入最小生成树，合并两棵树（即顶点i和顶点j所在的并查集）。
proc Union(i,j,c:longint); /*合并i和j所在集合*/
Var x,y:longint;
{ x←top(i); y←top(j); /*分别取出顶点i和顶点j所在子树的根*/
if x<>y Then { inc(ans,c);f[y]←x;}; /*若i和j分属于两棵子树，则该边权计入最小生成树的权和，两棵子树合并*/
};/* Union */
单击此处可添加副标题
按照边权值（c域值）递增的顺序排序边集e；
For i←1 to n Do f[i]←i; /*建立由n棵树组成的森林，每棵树包含图的一个顶点*/
ans←0; /* 最小生成树的权和初始化为0*/
For i←1 to m Do Union(e[i].x,e[i].y,e[i].c); /*枚举每条边，将两个端点分属两棵树的边加入最小生成树*/
Writeln(ans);
显然, Kruskal算法的效率取决于边数m,因此适用与稀疏图。
主算法
、Prim算法
集合A中的边总是只形成单棵树，每次添加到树中的边都是使树的权尽可能小的边。
设
d[i]—顶点i与生成树相连的最短边长；
ba[i]—顶点i在生成树的标志；
w[i,j]—（i,j）的边长。若图中不存在边（i,j），则w[i,j]=∞
min—所有未在生成树的顶点的最小距离值
fillchar(ba，sizeof(ba)，0)； /*所有顶点未在生成树*/
for i←2 to n do d[i]←∞； /*所有顶点的距离值初始化*/
d[1]←0 ；ans←0；/*顶点1的距离值和生成树的权和初始化*/
for i←1 to n do /*依次范围每个顶点*/
{ min←maxint；/*在所有未在生成树、且距离值最小（min）的顶点k*/
for j←1 to n do
if not ba[j]and(d[j]<min) then { k←j；min←d[j] }；/*then*/
if min= maxint then { ans←-1；break；}；/*若这样的顶点不存在，则无解退出*/
ans←ans+min；ba[k]←true；/*最小距离值min计入生成树的权和,顶点k进入生成树*/
for j←1 to n do /*调整与k相连的各顶点的距离值*/
{ min←w[k，j]；if min<d[j] then d[j]←min }；/*for*/
}；/*for*/
writeln(ans：0：3)； /*输出最小生成树的权和*/