[关闭]
@zqbinggong 2018-03-19T13:58:53.000000Z 字数 1437 阅读 349

chap23 最小生成树

最小生成树 Kruskal算法 Prim算法 算法导论

内容


最小生成树

  1. 假定有一个连通无向图和权重函数,需要找到这个图的最小生成树,无环子集,能将所有的点连接起来而且具有最小权重
  2. 本章的两种算法都是基于贪心策略的,具体的说,每个时刻生成最小生成树的一条边,并在整个策略实施过程中,管理一个下述循环不变的边集合A:

在每遍循环之前,A是某棵最小生成树的一个子集

generic-mst(G,w)

A = empty set
while A does not form a spanning tree
    find an edge (u,v) that is safe for A
    A = A U {(u,v)}
return A

问题的关键便是明确怎样的bian才是安全的,即能够保证

在每遍循环之前,A是某棵最小生成树的一个子集

定理23.1给出了安全边的规则

Let A be a subset of some MST, (S,V-S) be a cut that respects A, and (u,v) be a light edge crossing (S,V-S). Then(u,v) is safe for A.

是一个森林,其包含的每一个联通分量是一棵树,初始时,A为空,因而 中包含棵树,每棵树只有一个结点

推论23.2

If is a connected component in the forest is a light edge connecting C to some other component in (i.e., (u,v) is a light edge crossing the cut ), then (u,v) is safe for A.


Kruskal 和 Prim

  1. 在Kruskal中,集合A是一个森林,其结点就是给定图的结点,每次加入到集合A中的安全边永远是权重最小的连接两个不同分量的边,基于23.2
  2. 在Prim中,集合A是一棵树,每次加入的安全边都是连接A和A之外某个结点的边中权重最小的边,基于23.1
  3. 复杂度分析
    • Kruskal:
    • Prim:,如果使用菲波那切数列来实现Q,则为

mst-Kruskal(G,w)

A = enpty set
for each vertes v in G.V
    make-set(v)
sort the edges of G.E into nondecreasing by weight w
for each edge(u,v) in G.E,taken in nondecreasing order by weight
    if find-set(u) != find-set(v)
        A = A U {(u,v)}
        union(u,v)
return A

Prim算法中,多了一个输入参数r,它表示的是生成树的根结点,其中Q是基于key属性的最小优先队列,v.key表示连接结点v和树中结点的所有边中最小边的权重

mst-Prim(G,w,r)

for each u in G.V
    u.key = 00
    u.p = nil
r.key = 0
Q = G.V
while Q is not empty
    u = extract-min(Q)
    for each v in G.adj[u]
        if v in Q and w(u,v) < v.key
            v.p = u         #这一行将u连接的结点都设为u的孩子
            v.key = w(u,v)  #这一行最为关键,它会影响extract-min操作的结果

习题

to be continued


代码实现

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注