chap23 最小生成树

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

内容

最小生成树

1. 假定有一个连通无向图$G=(V,E)$和权重函数$w: E \rightarrow R$,需要找到这个图的最小生成树$T$，无环子集$T \subseteq E$，能将所有的点连接起来而且具有最小权重
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.

图$G_{A}=(V,A)$是一个森林，其包含的每一个联通分量是一棵树，初始时，A为空，因而$G_{A}$ 中包含$|V|$棵树，每棵树只有一个结点

推论23.2

If $C=(V_{C},E_{C})$ is a connected component in the forest $G_{A}=(V,A)$ is a light edge connecting C to some other component in $G_{A}$ (i.e., (u,v) is a light edge crossing the cut $(V_{C},V-V_{C})$), then (u,v) is safe for A.

Kruskal 和 Prim

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

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

代码实现