| Quick Links | |
| What's
New
Home Contacts Course Book Java Book JDK & JDSL Slides Notes Demos Exercises Marks |
|
The minimum spanning tree (MST) is a solution to the minimum connector problem. An example of the minimum connector problem might be as follows. We have to build an irrigation system (made of canals) connecting given locations. Some of these locations cannot be directly connected (maybe because of cost or geographical constraints). Design a system at minimum total cost.
We can take the locations as vertices of a graph, and the canals as the edges of the graph, where the edges are labelled with a weight, giving us the cost of constructing that canal. We must then find a subgraph that passes through each vertex. Clearly this subgraph must be a tree, because if it wasn't a tree it must contain a cycle, and the cycle can be broken by deleting an edge, reducing the cost, and not disconnecting the graph.
What follows are two algorithms that compute the MST, and a proof that they are correct.
Kruskal's Algorithm
This is a greedy algorithm, at each stage making the greediest possible
choice (ie. locally best) with no concern to the implications of this choice
on future choices. Such techniques generally do not deliver optimal solutions,
but in this case it does, and we give a proof of this.
Kruskal's algorithm can be stated as follows:
0. Create a minimum spanning tree T that initially contains no edges, 1. Choose an edge e in G, where (a) e is not in T and ... (b) e is of minimum weight and ... (c) e does not create a cycle in T 2. If T does not contain all the vertices of G go to step 1.The tree T, produced by the above algorithm, is a MST. We prove this by contradiction.
Proof of Kruskal's algorithm
Let T be a minimum spanning tree of G, and assume (wrongly, as we will
show) that there exists another minimum spanning tree S, such that weight
of S (ie. W(S)) is less than weight of T (ie. W(S) < W(T))
1. Let e be the edge of least weight in T that is not in S 2. Add edge e to S (a) This creates a cycle C, and C contains e (b) Cycle C contains an edge e', where e' is not in T. Proof: This must be the case otherwise all edges in C - e are already in T, and T would also contain a cycle, and would not be a tree. (c) If we replace e' in S by e we get a spanning tree S' where (i) cost of e <= cost e' Proof: e and e' must be coincident on one vertex in common, and the above algorithm would have chosen e in preference to e' to create T. (ii) S' is now one edge closer to T than S' is to T. 3. W(S') <= W(S). We can now repeat from step 1 until S' = T 4. Process terminates with S' = T and W(T) <= W(S). This contradicts initial assumption, that there can be another MST, S< of less cost than T. Consequently Kurskal's algorithm is sound.Prim's algorithm
In Prim's algorithm we deal with vertices rather than edges (a crude differentiation between Kruskal's algorithm, but a starting point at least). The algorithm goes as follows.
1. Put an arbitrary vertex into T 2. Add an edge e of minimum weight to T, where e joins a vertex in T to a vertex not in T.More specifically,
0. let U be the set of vertices in the minimum spanning tree T, and
initialise U to be the set {1}
let V-U be the set of vertices not in the minimum spanning tree, and
initialise V-U to be {2,3,4,...,n}
let T be the set of edges in the minimum spanning tree, and
initialise T to be the empty set {}
1. let e be the lowest cost edge in G that joins a vertex in U to a
vertex in V-U
2. Add edge e to T
3. let w be the (second e), ie w is the vertex in V-U that is
an end vertex of the edge e
4. Add vertex w to U
5. Remove vertex w from V-U
6. If the set V-U is not empty then go to step 1 otherwise deliver T
The above algorithm can be shown to be sound using a similar proof to the
one above.
Complexity of Prim
Assume the graph G is complete. At each iteration, step 1 compares
the distance of each of the vertices in U to each of the vertices in V-U.
Initially there will be 1 vertex in U and n-1 vertices in V-U, leading
to n-1 looks at edge weights. Next time round there will be 2 vertices
in U and n-2 vertices in V-U, and we examine 2(n-2) edges. Next time there
will be 3 vertices in U, (n-3) vertices in V-U and 3(n-3) edges will be
examined ... and so on. So we have
Sn = 1.(n-1) + 2(n-2) + 3(n-3) ... n(n-(n-1)) = n + 2n + 3n + 4n ... - (1 + 4 + 9 + 16 ...) = n(1 + 2 + 3 + 4 ...) - (1 + 4 + 9 + 16 ...) = (n*n*n - n*n - n)/6 = O(n*n*n)Therefore, for a complete graph, the above implementation of Prim's algorithm is of cubic complexity. However, using a heap data structure and a marking scheme similar to Dijkstra's algorithm, complexity reduces to O((n+m)log(n)). The main contribution to complexity comes from step 1, finding the lowest cost edge in G that joins a vertex in U to a vertex not in U (i.e. in V-U). When we add a vertex w to U in step 4, we could update a cost/distance d[x] from w to x, for all x adjacent to w in V-U. If d[x] reduces in cost we can update an attribute of x stating how we get to x (i.e. via the edge (w,x)), i.e. e[x]=w. We then change the overall structure somewhat, so that we now maintain a priority queue Q containing all the vertices in V-U prioritised with respect to d[x]. Therefore we process next the vertex closest to some vertex in U.
Prim Question
Here is a 1994 resit question on the MST.
Prim Demo
A scheme encoding of the above algorithm can be found in
prim.scm
When you load the file it will give a small guide to using a demo for Prim's
algorithm. This will create a complete graph of n vertices and will compute
the MST. As it goes it will draw out the edges of the MST. I would suggest
that you do not go beyond a graph with 100 vertices, as it take considerable
time to create the graph.