最小生成树
Minimum Spanning Trees
Given a undirected graph
A spanning tree of
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
- Adding
to MST creates a cycle. - Some other edge
in cycle must be a crossing tree. - Removing
and adding is also a spanning tree. - Since weight of
is less than the weight of , 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
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
我们来看看 Kruskal's algorithm 是如何划分两个点集 (即找到一个合法的 cut) 的。
- Suppose Kruskal's algorithm colors the edge
: - black. - Cut = set of vertices connected to
in tree . - In this cut we can guarentee that no crossing edge is black & no crossing edge has lower weight.
如图,根据 Kruskal 算法,当前的
对于该 cut,可以证明 0-2 是一个 minimum black-crossing edge。
- black-crossing edge:由于加入 0-2 不会使
中出现环, 中点 0 所在的连通块与点 2 所在的连通块本来是不连通的。因此 0-2 一定是一个 black-crossing edge。 - minimum:Kruskal 算法是按照边权由小到大的顺序考虑的,因此可以保证当前考虑的这条边一定是所有 crossing edge 中最小的。
Implementation Challenge. Kruskal 算法实现的难点在于动态判环:由于是否存在环本质上是一个判断是否联通的问题,我们可以轻易用并查集解决这个问题。
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; }
}
Single-link Clustering
接下来我们看一个似乎与 MST 不相关的问题 — single-link clustering 问题。首先介绍以下定义:
- k-clustering. Divide a set of objects classify into
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
我们对给出的点集构造出一张无向图,任意两点间的边权为它们之间的距离。
由于需要 clusters 之间的最小距离最大,我们采取贪心算法:由小到大考虑每一条边,若该边连接了两个不同的 clusters,则将这两个 clusters 聚合为一个 cluster,从而消除了该最小距离。重复以上过程直至图中只剩下
这本质上就是 Kruskal 算法求 MST 的过程。它微妙的印证了这样一个性质:对于一棵树,删掉该树中的
Prim's Algorithm
关于 Kruskal 算法与 Prim 算法的区别有一条十分精准的概括:Kruskal 是基于边 (edges) 的贪心算法,而 Prim 则是基于点 (vertices) 的贪心算法。
- Start with vertex 0 and greedily grow tree
. - Add to
the min weight edge with exactly one endpoint in . - Repeat until V-1 edges are added.
与 Kruskal 算法相同,Prim 算法也是 greedy MST algorithm 的一种 special case。它是这样划分点集的:
- Suppose edge
= 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.
如图,当前
由于 Prim 算法是逐渐对
Implementation Challenge. Find the min weight edge with exactly one endpoint in
Lazy Implementation
Lazy solution. Maintain a PQ of edges with (at least) one endpoint in
- Key = edge; priority = weight of edge.
- Delete-min to determine next edge
= - to add to . - Disregard if both endpoints
and are marked (both in ). - Otherwise, let
be the unmarked vertex (not in ): - add to PQ any edge incident to
(assuming other endpoint not in ) - add
to and mark .
- add to PQ any edge incident to
为何叫 lazy approach?因为 PQ 中维护的边并非所有都是只有一端在
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
- Delete min vertex
and add its associated edge = - to . - Update PQ by considering all edges
= - incident to . - case 1: ignore if
is already in . - case 2: add
to PQ if not already on it. - case 3: decrease priority of
if - becomes the shortest edge connecting to if in PQ but not in .
- case 1: ignore if
当点
对于每个元素,IPQ 为其分配一个整数索引,并维护三个数组 keys[], pq[] 与 qp[]。
keys[i]is the priority ofi.pq[i]is the index of the key in heap positioni.qp[i]is the heap position of the key with indexi.



