Spanning Trees: Introduction To Algorithms
Spanning Trees: Introduction To Algorithms
Spanning Trees: Introduction To Algorithms
Tree
We call an undirected graph a tree if the graph is connected and contains no cycles. Trees:
Not Trees:
Not connected
Has a cycle
Number of Vertices
If a graph is a tree, then the number of edges in the graph is one less than the number of vertices. A tree with n vertices has n 1 edges.
Note: Any node can be the root here, as we are not dealing with rooted trees.
Connected Graph
A connected graph is one in which there is at least one path between each pair of vertices.
Spanning Tree
In a tree there is always exactly one path from each vertex in the graph to any other vertex in the graph. A spanning tree for a graph is a subgraph that includes every vertex of the original, and is a tree.
(a) Graph G
Non-Connected Graphs
If the graph is not connected, we get a spanning tree for each connected component of the graph.
We could break the two cycles by removing a single edge from each. One of several possible ways to do this is shown below.
A spanning tree that has minimum total weight is called a minimum spanning tree for the graph.
If all edges have the same weight, breadth-first search or depth-first search will yield minimum spanning trees.
For the rest of this discussion, we assume the edges have weights associated with them.
Note, we are strictly dealing with undirected graphs here, for directed graphs we would want to find the optimum branching or aborescence of the directed graph.
Building cable networks that join n locations with minimum cost. Building a road network that joins n cities with minimum cost. Obtaining an independent set of circuit equations for an electrical network. In pattern recognition minimal spanning trees can be used to find noisy pixels.
Step i) requires N-1 time, since each tree will have exactly N-1 edges. If there are M spanning trees, then the total cost will O(MN). Consider a complete graph, with N(N-1) edges. How big can M be?
There are many approaches to computing a minimum spanning tree. We could try to detect cycles and remove edges, but the two algorithms we will study build them from the bottom-up in a greedy fashion. Kruskals Algorithm starts with a forest of single node trees and then adds the edge with the minimum weight to connect two components. Prims Algorithm starts with a single vertex and then adds the minimum edge to extend the spanning tree.
Kruskals Algorithm
Step 1 Step 2
Step 3
Step 4
Kruskals Algorithm
Use Kruskals algorithm to find a minimum spanning tree for the graph.
7 A 7.5 B 10 1.5
D
4.5 F 9.5 4 C 8 3
Kruskals Algorithm
Solution
First, choose ED (the smallest weight).
7
A 10
1 D
4.5 F 9.5
7.5
B
1.5
4
C 8
Kruskals Algorithm
Solution
Now choose BF (the smallest remaining weight).
7
A 10
1 D
4.5 F 9.5
7.5
B
1.5
4
C 8
Kruskals Algorithm
Solution
Now CD and then BD.
7
A 10
1 D
4.5 F 9.5
7.5
B
1.5
4
C 8
Kruskals Algorithm
Solution
Note EF is the smallest remaining, but that would create a cycle. Choose AE and we are done.
7
A 10
1 D
4.5 F 9.5
7.5
B
1.5
4
C 8
Kruskals Algorithm
Solution
The total weight of the tree is 16.5.
7
A 10
1 D
4.5 F 9.5
7.5
B
1.5
4
C 8
Kruskals Algorithm
Some questions:
1.
2.
1 D
4.5 F 9.5
7.5
B
1.5
4
C 8
Kruskals Algorithm
Build a priority queue (min-based) with all of the edges of G. T=; while(queue is not empty){ get minimum edge e from priorityQueue; if(e does not create a cycle with edges in T) add e to T; } return T;
Kruskals Algorithm
Steps
Initialize forest Sort edges Check edge for cycles O( |V| ) Number of edges O( |V| ) Total Since |E| = O( |V|2 )
Thus we would class MST as O( n2 log n ) for a graph with n vertices This is an upper bound, some improvements on this are known.
Kruskals Algorithm
Another implementation is based on sets (see Chapter 21). Kruskal() { T = ; for each v V MakeSet(v); sort E by increasing edge weight w for each (u,v) E (in sorted order) if FindSet(u) FindSet(v) T = T U {{u,v}}; Union(FindSet(u), FindSet(v)); }
Kruskals Algorithm
2 8 14 25
19 17 5 13 1 9
21
Kruskals Algorithm
2 8 14 25
19 17 5 13 1? 1 9
21
Kruskals Algorithm
2 8 14 25
19 17 5 13 1? 1 9
21
Kruskals Algorithm
2 8 14 25
19 17 5 13 1? 1 9
21
Kruskals Algorithm
2 8 14 25
19 17 5 13 1? 1 9
21
Kruskals Algorithm
2 8 14 25
19 17 5 13 1? 1 9
21
Kruskals Algorithm
2 8 14 25
19 17 5 13 1? 1 9
21
Kruskals Algorithm
2 8 14 25
19 17 5 13 1? 1 9
21
Prims Algorithm
Prims algorithm finds a minimum cost spanning tree by selecting edges from the graph one-by-one as follows: It starts with a tree, T, consisting of a single starting vertex, x. Then, it finds the shortest edge emanating from x that connects T to the rest of the graph (i.e., a vertex not in the tree T). It adds this edge and the new vertex to the tree T. It then picks the shortest edge emanating from the revised tree T that also connects T to the rest of the graph and repeats the process.
Prims Algorithm
2 8 14 25
19 17 5 13 1 9 Start here
21
Prims Algorithm
2 8 14 25
19 17 5 13 1? 1 9
21
Prims Algorithm
2 8 14 25
19 17 5 13 1 9
21
Prims Algorithm
2 8 14 25
19 17 5 13 1 9
21
Prims Algorithm
2 8 14 25
19 17 5 13 1 9
21
Prims Algorithm
2 8 14 25
19 17 5 13 1 9
21
Prims Algorithm
2 8 14 25
19 17 5 13 1 9
21
Prims Algorithm
2 8 14 25
19 17 5 13 1 9
21
It is not necessary that Prim's and Kruskal's algorithm generate the same minimum-cost spanning tree. For example for the graph shown on the right: Kruskal's algorithm results in the following minimum cost spanning tree:
The same tree is generated by Prim's algorithm if the start vertex is any of: A, B, or D.
However if the start vertex is C the minimum cost spanning tree generated by Prims algorithm is:
Implementation Details
Prims Algorithm from your book is horrible from a SE stand-point! MST-Prim(G, w, r) Q is a priority queue Q = V[G]; key is the internal priorities in Q! for each u Q changing key, changes the queue. key[u] = ; key[r] = 0; p[r] = NULL; while (Q not empty) u = ExtractMin(Q); for each v Adj[u] if (v Q and w(u,v) < key[v]) p[v] = u; key[v] = w(u,v);
Implementation Details
Why queue the vertices, rather than the newly discovered edges? MST-Prim(G, w, r) Q = V[G]; A Fibonacci Heap allows this to be for each u Q done in O(1) time. key[u] = ;
DecreaseKey(r, 0);
p[r] = NULL; while (Q not empty) u = ExtractMin(Q); for each v Adj[u] if (v Q and w(u,v) < key[v]) p[v] = u;
DecreaseKey(v, w(u,v));
Cornwell
8
Avenford
6 8
Fingley
Donster
7 4
5
2
Edan
A B C D E F
A 3 4 7
B 3 5 8
C 5 4 6
D 4 2 8
E 4 2 5
F 7 8 6 8 5 -
Start at vertex A. Label column A 1 . Delete row A Select the smallest entry in column A (AB, length 3)
Brinleigh
3
Avenford
A B C D E F
A 3 4 7
B 3 5 8
C D - 5 - 4 4 - 2 6 8
E 4 2 5
F 7 8 6 8 5 -
1
Label column B 2 Delete row B Select the smallest uncovered entry in either column A or column B (AE, length 4)
Brinleigh
3
Avenford
A B C D E F
A 3 4 7
B 3 5 8
C D - 5 - 4 4 - 2 6 8
E 4 2 5
F 7 8 6 8 5 -
4
Edan
Label column E 3 Delete row E Select the smallest uncovered entry in either column A, B or E (ED, length 2)
Brinleigh
3
Avenford
A B C D E F
Donster
A 3 4 7
B 3 5 8
C D - 5 - 4 4 - 2 6 8
E 4 2 5
F 7 8 6 8 5 -
4
Edan
1
Label column D 4 Delete row D Select the smallest uncovered entry in either column A, B, D or E (DC, length 4)
Brinleigh
Cornwell
3
Avenford
A B C D E F
Donster
A 3 4 7
B 3 5 8
C D - 5 - 4 4 - 2 6 8
E 4 2 5
F 7 8 6 8 5 -
4
Edan
1
Label column C 5 Delete row C Select the smallest uncovered entry in either column A, B, D, E or C (EF, length 5)
Brinleigh
Cornwell
3
Fingley
Avenford
A B C D E F
Donster
A 3 4 7
B 3 5 8
C D - 5 - 4 4 - 2 6 8
E 4 2 5
F 7 8 6 8 5 -
5 4
Edan
1
FINALLY Label column F 6 Delete row F
Brinleigh
Cornwell
3
Fingley
Avenford
A B C D E F
Donster
A 3 4 7
B 3 5 8
C D - 5 - 4 4 - 2 6 8
E 4 2 5
F 7 8 6 8 5 -
5 4
Edan
1
FINALLY Label column F 6 Delete row F
Brinleigh
Cornwell
3
Fingley
Avenford
A B C D E F
Donster
A 3 4 7
B 3 5 8
C D - 5 - 4 4 - 2 6 8
E 4 2 5
F 7 8 6 8 5 -
5 4
Edan
Practice
GB
1. Find the breadth-first spanning tree and depth-first spanning tree of the graph GA shown above. 2. For the graph GB shown above, trace the execution of Prim's algorithm as it finds the minimum-cost spanning tree of the graph starting from vertex a. 3. Repeat question 2 above using Kruskal's algorithm.
Practice
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
List the edges in increasing order: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Starting from the left, add the edge to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point. Notice that the edge of weight 45 would close a circuit, so we skip it. 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
115
90
52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
Add the next edge in the list to the tree if it does not close up a circuit with the edges chosen up to that point: 20, 25, 30, 32, 35, 38, 40, 45, 50, 52, 55, 60, 70, 70, 88, 90, 100, 110, 115, 120
Done!
115 90 52
40 100 50
55 110 120
35
20
45
32 60 88 38
25
30
70
70
The tree contains every vertex, so it is a spanning tree. The total weight is 395
Both take the next minimum edge Both are optimal (find the global min) Kruskal all edges Prim Edges from Tree nodes to rest of G. Kruskal set containment and union. Prim Simple boolean. Kruskal when |V|-1 edges are added. Prim when |V| nodes are added (or |V|-1 edges). Prim can be O( |E| + |V| log|V| ) w/ Fibonacci Heaps Prim with an adjacency matrix is O(|V|2).