«

[算法导论笔记]最小生成树

在一个连通的无向图G=(V,E)中,找到一个无环子集T(是E的子集),既能够将所有的结点连接起来,又具有最小的权重,这时的T便成为最小生成树。

解决最小生成树的两个常用算法为:Kruskal算法和Prim算法。如果使用普通的二叉堆,这两个算法的时间复杂度最小为O(ElgV)。但如果使用斐波那契堆,Prim算法的时间复杂度将改善为O(E+VlgV)。

基本策略:
GENERIC-MAT(G, w)  
  A = Empty  
  while A does not form a spanning tree  
      find an edge(u, v)that is safe for A  
      A = A ∪ {(u, v)}  
  return A  
Krushkal 算法:
MST-KRUSKAL(G, w)  
  A = Empty  
  for each vertex v∈G.V  
      MAKE-SET(v)  
  sort the edges of G.E into nondecreasing order by weight w  
  for each edge(u,v)∈G.E, taken in nondecreasing order by weight  
      if FIND-SET(u) ≠ FIND-SET(v)  
          A = A ∪ {(u, v)}  
          UNION(u, v)  
  return A  
Prim 算法:
MST-PRIM(G, w, r)  
  for each u∈G.V  
      u.key = ∞  
      u.π = NIL  
  r.key = 0  
  Q = G.V  
  while Q ≠ Empty  
      u = EXTRACT-MIN(Q)  
      for each v∈G.Adj[u]  
        if v∈Q and w(u, v) < v.key  
            v.π = u  
            v.key = w(u, v)  
分享