最小生成树ppt课件.ppt

4．最小生成树及算法
1) 树(tree)的定义与树的特征
定义 连通且不含圈的无向图称为树．常用T表示.
树中的边称为树枝. 树中度为1的顶点称为树叶.
孤立顶点称为平凡树.
平凡树
注意：无向图
例如，图 . 为无圈图，
ii) 是满足i)的尽可能小的权，
3) 当第2)步不能继续执行时，则停止.
定理4 由Kruskal算法构作的任何生成树
都是最小树.
Kruskal算法步骤
(1) 对属于E的边进行排序得
(2) 初始化操作
（3）若t=n-1,则转（6），否则转（4）
（4）若
（6）输出T，w，停止
例10用Kruskal算法求下图的最小树.
在左图中 权值
最小的边有 任取一条
在 中选取权值
最小的边
中权值最小边有 , 从中选
任取一条边
会与已选边构成圈,故停止,得
中选取在中选取
中选取 . 但 与 都
最小生成树的Prim算法
Prim算法思路
从任意一顶点开始，首先把这个顶点包括在生成树里，然后在那些其一端已在生成树里，而另一端还未在生成树里的边中，找权值最小的一条边，并把这条边和其不在生成树里的那个顶点包括进生成树中。如此进行下去，每次往生成树里加入一个顶点和一条权最小的边，直到把所有顶点都包括进生成树里
理论上，当有两条具有相同最小权值的边可选择时，选哪一条都行，因此构造的最小生成树不一定唯一。但若给定算法，则唯一
Prim 算法的参考步骤
第一步 T0，w(T0)0，V {v0}。
第二步 对每一个点 vV  V ，L(v)w(v, v0)（如果 (v, v0)E，则 w(v, v0) = ）。
第三步 如果 V  = V，输出 T0，w(T0)，停止。否则进行下一步。
第四步 在 V  V 中找一点 u，使
L(u) = min{L(v) | vV  V }，
并将 V  中与 u 邻接的点记为 x，e = (x, u)。
第五步 T0T0{e}，w(T0)w(T0)+w(e)，
V V {u}。
第六步 对所有 vVV ，如 w(v, u) < L(v)，则 L(v) w(v, u)，否则 L(v) 不变。
第七步 转第三步。
步骤
u
L(b)
L(c)
L(d)
L(e)
L(f)
L(g)
e
V 
T0
C(T0)
1
a
4
15

7

28
{a}

0
2
b
－
9

7

28
(a,b)
{a, b}
{(a, b)}
4
3
e
－
5
32
－

28
(a,e)
{a, b, e}
{(a, b), (a, e)}
11
4
c
－
－
25
－

28
(c,e)
{a, b, e, c}
{(a, b), (a, e), (c, e)}
16
5
d
－
－
－
－
16
12
(c,d)
{a, b, e, c, d}
{(a, b), (a, e), (c, e), (c, d)}
41
6
g
－
－
－
－
16
－
(d,g)
{a, b, e, c, d, g}
{(a, b), (a, e), (c, e), (c, d), (d, g)}
53
7
f
－
－
－
－
－
－
(d, f)
{a, b, e, c, d, g, f}
{(a, b), (a, e), (c, e), (c, d), (d, g), (d, f)}
69
从顶点a开始
结果显示于
图
最小生成树的 Kruskal 算法是 1956 年由Kruskal 提出的。随后在 1957 年，领导贝尔实验室数学研究室的 Prim 创立了他的算法。
Kruskal 算法的时间复杂性以 O(mlog2m) 为界，当边数较多或是一个完全图时，m  (n 1)2，则时间复杂性近似于 O(n2log2n)。而 Prim 算法的时间复杂性为O(n2)，所以，如果图的连通度较高（最高为完全图），以 Prim 算法较好，如果图的连通度较低，特别当 m  O(n) 时，则 Kr