Princeton COS 423 - Notes on Minimum Spanning Trees

Unformatted text preview:

COS 423 Notes on Minimum Spanning Trees Spring 2009 1. The Generic Greedy Algorithm The generic greedy algorithm finds a minimum spanning tree (MST) by an edge-coloring process. Initially all edges are uncolored. The algorithm colors edges blue (accepted) or red (rejected) one-at-a-time by repeatedly applying either of the following two coloring rules, in any order: Blue Rule: Given a cut that no blue edges cross, select a minimum uncolored edge crossing the cut, and color it blue. (A cut is a partition of the vertices into two non-empty parts; an edge crosses the cut if it has one end in each part.) Red Rule: Given a cycle containing no red edges, select a maximum uncolored edge on the cycle, and color it red. Termination: As long as at least one edge is uncolored, some edge can be colored by one of the rules. That is, the algorithm eventually colors all the edges, no matter in what order it applies the rules. Proof: Suppose some edge { , }v wis uncolored. Let X be the set of vertices reachable from v by traversing only blue edges, and let X be the remaining vertices. If w is in X, then { , }v wis on a cycle all of whose other edges are blue, and the red rule applies to color { , }v w red. Otherwise, X, X is a cut that {v, w} but no blue edges cross. Thus the blue rule applies to color { , }v wor some other edge blue. QED Correctness: The algorithm maintains the invariant that some MST T contains all of the blue edges and none of the red ones. Proof: By induction on the number of edges colored. The invariant is vacuously true initially, since no edges are colored and any MST satisfies the invariant. Suppose the invariant holds for an MST T before an application of the blue rule that colors a minimum edge { , }v wcrossing a cut X, X. If { , }v w is in T, the invariant holds for T after { , }v w is colored. Otherwise, consider the cycle formed by adding { , }v w to T. This cycle contains at least one edge { , }x y in T crossing X, X. (It may contain several.) Edge { , }x y must be uncolored since it crosses the cut, so it has cost at least as large as { , }.v w But adding { , }v w to T and deleting { , }x y forms a new spanning tree T', which has cost no more than that of T. Since T is minimum, T' must also be minimum (and { , }v w and { , }x y must have the same cost). Tree T' satisfies the invariant after { , }v w is colored. Suppose the invariant holds for an MST T before an application of the red rule that colors a maximum edge{ , }v won a cycle C. If { , }v w is not in T, the invariant holds for T after{ , }v w is colored. Otherwise, deleting { , }v w from T produces two trees. At least one edge { , }x y of C other than { , }v w must have exactly one end in each of these trees. Edge { , }x y cannot be blue because it is not in T, and it cannot be red since C contains no red edges, so it must be uncolored. Since the red rule applies to color { , },v w { , }v w has cost no less than that of { , }.x y But deleting { , }v w from T and adding { , }x y forms a new tree T'. Since T is an MST, T' must also be an MST and { , }v w and { , }x y must have equal cost. Tree T' satisfies the invariant after { , }v w is colored. QED The invariant implies that once all edges are colored (or even once the blue edges form a single tree), the blue edges form an MST. The proof also implies that if all edge costs are distinct, there is a unique MST. (Why?) 2. Three Classical Algorithms The generalized greedy algorithm is highly non-deterministic in that the coloring rules can be applied in any order. There are three classical MST algorithms that are specializations of the generic algorithm, two of them well-known and one much less so. In describing these algorithms, I shall use the term “blue tree” to refer to any of the maximal trees defined by the blue edges. (By the invariant, the blue edges can never contain a cycle.) Initially there are n one-vertex blue trees. Each time an edge is colored blue, two blue trees are combined into one, until after 1n− edges are colored blue, there is only one blue tree, which is an MST. 2.1. Kruskal's Algorithm Kruskal's algorithm (1956) is globally greedy: examine the edges in non-decreasing order by cost. When examining an edge { , },v w color it blue if its ends are in different blue trees and red otherwise. (Prove that this algorithm is a specialization of the generic algorithm.) To implement Kruskal's algorithm efficiently, we need two things: a mechanism for selecting edges in non-decreasing order by cost, and a way to keep track of the vertex sets of the blue trees. The latter is an instance of the disjoint set union problem, and the compressed-tree data structure solves it. There are at most two finds per edge and exactly 1n− links, for a total time of O( ( , )).m m nα To select edges in non-decreasing order by cost, we can either sort the edges by cost or use a heap. If we use a binary-comparison-based method, the time bound for selecting edges will be O( log ) O( log ).m m m n= Using sorting has the advantage that the constant factor is small; using a heap has the advantage that on a dense graph we may have to delete only a small fraction of the edges from the heap before the MST is completed, resulting in a running time smaller than the worst-case bound. One intriguing possibility is to use an incremental version of quicksort that only does work as needed to determine the next edge to process. Such a method has a low constant factor and takes advantage of early completion of the MST. The bottleneck in Kruskal's algorithm is the time to order the edges, unless the edges are given in sortedorder or can be sorted fast, for example by using radix sorting. Then the bottleneck is the set maintenance, and the overall running time is O( ( , )).m m nα rather than O( log ).m n 2.2. The Algorithm of Jarník, Prim, and Dijkstra The other well-known classical algorithm is generally credited to Prim (1957) and Dijkstra (1959) independently, but was actually discovered by Jarník (1930). The JPD algorithm is a single-source version of the generic algorithm: it grows a single blue tree from a fixed starting vertex s (the source). …


View Full Document

Princeton COS 423 - Notes on Minimum Spanning Trees

Download Notes on Minimum Spanning Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Notes on Minimum Spanning Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Notes on Minimum Spanning Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?