最小生成树

Minimum Spanning Trees

Given a undirected graph GG with positive edges weights (connected).

A spanning tree of GG is a subgraph TT that is both a tree (connected and acyclic) and spanning (includes all of the vertices).

Our goal is to find a min weight spanning tree, i.e., minimum spanning tree.

Cut Property

We make the simplifying assumptions: (1) Edge weights are distinct. (2) Graph is connected. Under such assumptions MST exists and is unique.

A cut in a graph is a partiton of its vertices into two nonempty sets. A crossing edge connects a vertex in one set with a vertex in the other.

如图,cut 将顶点分为灰色与白色两个点集,所有连接这两个点集的边都是 crossing edge。MST 有这样一个性质:Given any cut, the crossing edge of min weight is in the MST.

我们用反证法对该性质进行证明:假设 min-weight crossing edge ee 并不在 MST 中。

  • Adding ee to MST creates a cycle.
  • Some other edge ff in cycle must be a crossing tree.
  • Removing ff and adding ee is also a spanning tree.
  • Since weight of ee is less than the weight of ff, that spanning tree is lower weight.
  • Contradiction!

Greedy MST Algorithms

利用 MST 的 cut property,我们能设计这样一个理论上的贪心算法:

  • Start with all edges colored gray.
  • Find cut with no black crossing edges; color its min-weight edge black.
  • Repeat until V−1V-1 edges are colored black.

该算法的 crucial 之处在于如何找到一种划分点集的方法 (即 cut),并且点集之间没有 black crossing edges。接下来我们将介绍两种划分的算法:Kruskal 算法与 Prim 算法。

Kruskal's Algorithm

Kruskal's algorithm considers edges in ascending order of weight. We add next edge to tree TT unless doing so would create a cycle. If V-1 edges is added, TT is spanned to MST.

我们来看看 Kruskal's algorithm 是如何划分两个点集 (即找到一个合法的 cut) 的。

  • Suppose Kruskal's algorithm colors the edge ee: vv-ww black.
  • Cut = set of vertices connected to vv in tree TT.
  • In this cut we can guarentee that no crossing edge is black & no crossing edge has lower weight.

如图,根据 Kruskal 算法,当前的 TT 中包括边 1-7,7-0 与 2-3,下一个被添加的边为 0-2。如果加入 0-2 不会令 TT 中出现环,一个合法的 cut 为 {1,7,0}\{1,7,0\} (TT 中与 0 连接的所有点) 与 {2,3,4,5,6}\{2,3,4,5,6\}。

对于该 cut,可以证明 0-2 是一个 minimum black-crossing edge。

  • black-crossing edge:由于加入 0-2 不会使 TT 中出现环,TT 中点 0 所在的连通块与点 2 所在的连通块本来是不连通的。因此 0-2 一定是一个 black-crossing edge。
  • minimum:Kruskal 算法是按照边权由小到大的顺序考虑的,因此可以保证当前考虑的这条边一定是所有 crossing edge 中最小的。

Implementation Challenge. Kruskal 算法实现的难点在于动态判环:由于是否存在环本质上是一个判断是否联通的问题,我们可以轻易用并查集解决这个问题。

java
public class KruskalMST {
    private Queue<Edge> mst = new Queue<Edge>();
    
    public KruskalMST(EdgeWeightedGraph G) {
        MinPQ<Edge> pq = new MinPQ<Edge>();
        for (Edge e : G.edges())	pq.insert(e);
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin();
            int v = e.either(), w = e.other(v);
            if (!uf.connected(v, w)) {
                uf.union(v, w);
                mst.enqueue(e);
            }
        }
    }
    public Iterable<Edge> edges() { return mst; }
}

接下来我们看一个似乎与 MST 不相关的问题 — single-link clustering 问题。首先介绍以下定义:

  • k-clustering. Divide a set of objects classify into kk conherent groups.
  • Distance function. Numeric value specifying "closeness" of two objects.

一个常见的 distance function 定义是 single-link definition: Distance between two clusters equals the distance between the two closest objects (one in each cluster).

那么我们定义 single-link clustering 问题如下:Given an integer kk, find a k-clustering that maximizes the distance between two closest clusters.

我们对给出的点集构造出一张无向图,任意两点间的边权为它们之间的距离。

由于需要 clusters 之间的最小距离最大,我们采取贪心算法:由小到大考虑每一条边,若该边连接了两个不同的 clusters,则将这两个 clusters 聚合为一个 cluster,从而消除了该最小距离。重复以上过程直至图中只剩下 kk 个 clusters,我们能够保证这 kk 个 clusters 间的最小距离最大。

这本质上就是 Kruskal 算法求 MST 的过程。它微妙的印证了这样一个性质:对于一棵树,删掉该树中的 k−1k-1 条边,最后将会得到 kk 个连通块。

Prim's Algorithm

关于 Kruskal 算法与 Prim 算法的区别有一条十分精准的概括:Kruskal 是基于边 (edges) 的贪心算法,而 Prim 则是基于点 (vertices) 的贪心算法。

  • Start with vertex 0 and greedily grow tree TT.
  • Add to TT the min weight edge with exactly one endpoint in TT.
  • Repeat until V-1 edges are added.

与 Kruskal 算法相同,Prim 算法也是 greedy MST algorithm 的一种 special case。它是这样划分点集的:

  • Suppose edge ee = min weight edge connecting a vertex on the tree.
  • Cut = set of vertices connected on tree.
  • In this cut we can guarentee that no crossing edge is black & no crossing edge has lower weight.

如图,当前 TT 中的边包括 1-7, 7-0, 0-2 与 2-3,下一个加入的边为 7-5。此时一个合法的 cut 为 {1,7,0,2,3}\{1,7,0,2,3\} (即 TT 本身) 与 {4,5,6}\{4,5,6\}。

由于 Prim 算法是逐渐对 TT 进行扩展的,TT 一定是联通的。因此,任何连接 TT 与非 TT 节点的边都一定是 crossing edge。又我们是按照权值由小到大进行考虑的,该 crossing edge 一定是 minimum 的。

Implementation Challenge. Find the min weight edge with exactly one endpoint in TT.

Lazy Implementation

Lazy solution. Maintain a PQ of edges with (at least) one endpoint in TT.

  • Key = edge; priority = weight of edge.
  • Delete-min to determine next edge ee = vv-ww to add to TT.
  • Disregard if both endpoints vv and ww are marked (both in TT).
  • Otherwise, let ww be the unmarked vertex (not in TT):
    • add to PQ any edge incident to ww (assuming other endpoint not in TT)
    • add ee to TT and mark ww.

为何叫 lazy approach?因为 PQ 中维护的边并非所有都是只有一端在 TT 中的。随着 TT 的生长,PQ 中的某些边会变得 obsolete (两端都在 TT 中)。因此从 PQ 中取边时需要加入判断,舍弃已经变得 obsolete 的边。

java
public class LazyPrimMST {
    private boolean[] marked;       // MST vertices
    private Queue<Edge> mst;        // MST edges
    private MinPQ<Edge> pq;         // PQ of edges
    
    public LazyPrimMST(WeightedGraph G) {
        pq = new MinPQ<Edge>();
        mst = new Queue<Edge>();
        marked = new boolean[G.V()];
        visit(G, 0);                      // assume G is connected: add vertex 0 to T
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin();
            int v = e.either(), w = e.other(v);
            if (marked[v] && marked[w])  continue;  // disgard obsolete edges
            mst.enqueue(e);                         // add edge e to tree T
            if (!marked[v])  visit(G, v);           // add the not-in-T endpoint to T
            if (!marked[w])  visit(G, w);
        }
    }
    
    private void visit(WeightedGraph G, int v) {
        marked[v] = true;               // add v to T
        for (Edge e : G.adj(v))
            if (!marked[e.other(v)])    // for each edge v-w, add to PQ if w not already in T
                pq.insert(e);         
    }
    
    public Iterable<Edge> mst() { return mst; }
}

Eager Implementation

eager approach 同样维护一个 PQ,但与 lazy approach 不同的是 PQ 中维护的是点,而非边。

Maintain a PQ of vertices connected by an edge to TT, where priority of vertex vv = weight of shortest edge connecting vv to TT. (是不是有点像最短路算法的思路?)

  • Delete min vertex vv and add its associated edge ee = vv - ww to TT.
  • Update PQ by considering all edges ee = vv - xx incident to vv.
    • case 1: ignore if xx is already in TT.
    • case 2: add xx to PQ if not already on it.
    • case 3: decrease priority of xx if vv-xx becomes the shortest edge connecting xx to TT if xx in PQ but not in TT.

当点 xx 到 TT 的距离被更新时,我们需要降低其优先级 (e.g., 修改 PQ 中储存的距离值):这就涉及到对 PQ 内部元素的操作。实现这一功能的数据结构称为 Indexed priority queue (索引优先队列)。

对于每个元素,IPQ 为其分配一个整数索引,并维护三个数组 keys[], pq[] 与 qp[]。

  • keys[i] is the priority of i.
  • pq[i] is the index of the key in heap position i.
  • qp[i] is the heap position of the key with index i.
CC BY-NC-SA 4.0
正在加载评论…