@zqbinggong
2018-03-19T21:58:53.000000Z
字数 1437
阅读 908
最小生成树
Kruskal算法
Prim算法
算法导论
在每遍循环之前,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.
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操作的结果