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

计算最小生成树的思维方向：为了保证边权总和最小，必须保证
①、添加(u,v)不能够形成回路、
②、在保证１的前提下添加权尽可能小的，这样的边称之为安全边
有两种算法可计算图的最小生成树
①、Kruskal算法
②、Prim算法
*
数据结构15--最小生成树
*
①、Kruskal算法
找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。初始时，森林由单个结点组成的n棵树。
*
数据结构15--最小生成树
*
Kruskal程序
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所在并查集的代表顶点，即子树根*/
*
数据结构15--最小生成树
*
通过函数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*/
*
数据结构15--最小生成树
*
通过过程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 */
*
数据结构15--最小生成树
*
主算法
按照边权值（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,因此适用与稀疏图。
*
数据结构15--最小生成树
*
②、Prim算法
集合A中的边总是只形成单棵树，每次添加到树中的边都是使树的权尽可能小的边。
*
数据结构15--最小生成树
*
设
d[i]—顶点i与生成树相连的最短边长；
ba[i]—顶点i在生成树的标志；
w[i,j]—（i,j）的边长。若图中不存在边（i,j），则w[i,j]=∞
min—所有未在生成树的顶点的最小距离值
*
数据结构15--最小生成树
*
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) t