#10. Minimum Spanning Tree

Given: Undirected Graph G with positive edge weights (connected)

Definition: A spanning tree of G is a subgraph that is both a tree (connected and acyclic) and spanning (includes all the vertices)

Goal: Find a spanning tree with minimum weight

下面两种Algorithm都属于Greedy algorithm

#10.1 Kruskal’s Algorithm

利用Union Find.

  1. Sort all edges by weight
  2. Add next edge to Tree unless its creating a cycle (Union-Find)

#Performance

Time: O(E * log(E))

构建minHeap的过程其实是O(E). 但是之后按次序遍历每条edge并把它加入tree, 是O(E * log(E))的操作. 因为union-find可以保证union和find都是O(log(E)

Java Kruskal’s Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class KruskalMST {
private class Edge {
int v;
int w;
int weight;
public Edge(final int v, final int w, final int weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
}
public static Queue<Edge> mstByKruskal(final Map<Integer, Map<Integer, Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Queue<Edge> mst = new LinkedList<>();
final PriorityQueue<Edge> minHeap = new PriorityQueue<>((x, y) -> x.weight - y.weight);
// 因为MST只作用于Undirected Graph. 所以在处理Edge的时候需要去重.
for (final int v : graph.keySet()) {
if (!visited.contains(v)) {
addEdgeToMinHeap(v, graph, visited, minHeap);
}
}
while (!minHeap.isEmpty()) {
final Edge edge = minHeap.poll();
if (!uf.find(edge.v, edge.w)) {
uf.union(edge.v, edge.w);
mst.offer(edge);
}
}
return mst;
}
private void addEdgeToMinHeap(final int v, final Map<Integer, Map<Integer, Integer>> graph, final Set<Integer> visited, final PriorityQueue<Edge> minHeap) {
visited.add(v);
for (final int adj : graph.get(v).keySet()) {
if (!visited.contains(adj)) {
minHeap.offer(new Edge(v, adj, graph.get(v).get(adj)));
addEdgeToMinHeap(adj, graph, visited, minHeap);
}
}
}
}

Python Kruskal’s Algorithm

TODO

1
2

#10.2 Prim’s Algorithm

  • Prims’s Algorithm Works best for dense graph
  • lazy version has runtime O(E * log(E))
  • eager version has runtime O(E * log(V))

#Algorithm

  1. Start with vertex 0 and greedily grow tree.
  2. Add to tree the minimum weight edge with exactly one endpoint in tree.
  3. Repeat until V - 1 edges.

#10.2.1 Lazy Implementation

1
2
Time: O(E * log(E))
Space: O(E)
  • Maintain priority queue by Edges, 和Kruskal’s Algorithm一样, 需要维护一个MinHeap,
  • 但是和Kruskal Algorithm不一样的是, 不需要把所有Edge都一股脑的先加到PriorityQueue里面.
  • 因为我们每次要找的Edge得保证至少一个endpoint在tree里, 所以在minHeap里的东西只需要是所有跟当前mst connect的edges即可.
  • 最终的结果mst可以有多种返回方式, 比如:
    1. 可以返回一个Queue
    2. 也可以返回一个Set
  • 如果是返回一个Set的话, 因为mst的定义就是要包含图中所有vertices, 所以如果mst就可以把它当做visited来用. 而如果mst是一个Queue, 那么需要另外一个visited的数据结构来记录访问情况.

Java Prim’s Lazy Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class LazyPrimMST {
public static Queue<Edge> mstByLazyPrims(final Map<Integer, Map<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final PriorityQueue<Edge> minHeap = new PriorityQueue<>((x, y) -> x.weight - y.weight);
final Queue<Edge> mst = new LinkedList<>();
final Set<Integer> visited = new HashSet<>();
// Start with any ONE of the vertices
for (final int v : graph.keySet()) {
visit(v, graph, minHeap, mst, visited);
break;
}
while (!minHeap.isEmpty()) {
final Edge edge = minHeap.poll();
if (visited.contains(edge.v) && visited.contains(edge.w)) {
continue;
} else {
mst.offer(edge);
if (!visited.contains(edge.v)) visit(edge.v);
if (!visited.contains(edge.w)) visit(edge.w);
}
}
return mst;
}
private static void visit(final int v, final Map<Integer, Map<Integer, Integer>> graph, final PriorityQueue<Edge> minHeap, final Set<Integer> visited) {
visited.add(v);
for (final int adj : graph.get(v)) {
if (!visited .contains(adj)) {
minHeap.offer(new Edge(v, adj, graph.get(v).get(adj)));
}
}
}
}

Python Prims’s Lazy Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def lazy_prim(graph):
"""
:type grpah: Dict[int, Dict[int, int]] adjacency list representing a weighted undirected graph
:rtype: int, the cost of mst
"""
if not graph:
raise Exception("invalid graph")
hp, mst = [], []
visited, nodes = set(), set()
for v in graph:
for w in graph[v]:
nodes.add(v)
nodes.add(w)
start = next(iter(nodes))
visited.add(start)
mst.append(start)
for adj in graph[start].keys():
if adj not in visited:
heapq.heappush(hp, (graph[start][adj], adj))
cost = 0
while hp:
curr = heapq.heappop(hp)
weight, node = curr[0], curr[1]
if node not in visited:
cost += weight
visited.add(node)
mst.append(node)
if len(mst) == len(nodes):
break
for adj in graph[node].keys():
if adj not in visited:
heapq.heappush(hp, (graph[node][adj], adj))
return cost

#10.2.2 Eager Implementation

1
2
Time: O(E * log(V))
Space: O(V)
  • Maintain priority queue of Vertices.
  • Eager Implementation 需要利用IndexHeapupdate priority. 因为这个方法是将vertex存在priority queue中, 排序方式是vertex与mst之间的weight.

举个栗子:
比如 v - w 的weight是5, v在mst中, w不在. 因为w connected to mst, 所以w结点现在应该在MinHeap中. 假设MinHeap中的top结点是x, x和w之间也有一条边, weight是1。那么当把x加入mst之后, 我们要更新w和tree之间的weight, 从原来的5变为更小的1.

Java Prim’s Eager Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class EagerPrimMST {
public static Queue<Edge> mstByEagerPrims(final Map<Integer, Map<Integer, Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final IndexHeap<Integer> minIndexHeap = new IndexHeap<>((x, y) -> x.weight - y.weight);
final Queue<Edge> mst = new LinkedList<>();
final Set<Integer> visited = new HashSet<>();
// Store the minimum weight edge from a vertex to current MST
// Not every edge to a vertex!
final Map<Integer, Edge> vertexToMinWeightEdge = new HashMap<>();
// Start with any one of the vertices
for (final int v : graph.keySet()) {
minIndexHeap.decreaseKey(v, 0);
break;
}
while (!minIndexHeap.isEmpty()) {
final int v = minIndexHeap.poll();
visited.add(v);
// vertexToMinWeightEdge存放的是结点v到当前mst中weight最小的edge.
if (vertexToMinWeightEdge.containsKey(v)) {
mst.offer(vertexToMinWeightEdge.get(v));
}
for (final int adj : graph.get(v)) {
// 之所以没有直接negate condition而是要continue,
// 是因为想要强调obsolete edges的概念.
if (visited.contains(adj)) continue; // Obsolete edge
if (graph.get(v).get(adj) < minIndexHeap.getWeight()) {
if (minIndexHeap.contains(adj)) {
minIndexHeap.decreaseKey(adj, graph.get(v).get(adj));
} else {
minIndexHeap.add(adj, graph.get(v).get(adj));
}
vertexToMinWeightEdge(adj, new Edge(v, adj, graph.get(v).get(adj)));
}
}
}
return mst;
}
}

Comments

01/03/2020