m |
m |
||
| Line 53: | Line 53: | ||
The cut property states that given any cut in the graph, the cheapest crossing edge must be in the MST. | The cut property states that given any cut in the graph, the cheapest crossing edge must be in the MST. | ||
| + | <br /> | ||
Proof: Assume distinct edge weights, although it is clear that if two edges are both the cheapest, either can be included. The proof is by contradiction. Define e to the cheapest crossing edge and let T* be the MST. Suppose T* does not contain e. Then T* must contain some other crossing edge f(since the MST is connected). If we add e to T*, we now get a cycle. Since e was defined to be the cheapest crossing edge, we can remove f from T* and we now have an MST of lower weight (removing an edge in a cycle doesn't affect connectedness). But this is a contradiction to the definition of T* meaning e must be in T*. | Proof: Assume distinct edge weights, although it is clear that if two edges are both the cheapest, either can be included. The proof is by contradiction. Define e to the cheapest crossing edge and let T* be the MST. Suppose T* does not contain e. Then T* must contain some other crossing edge f(since the MST is connected). If we add e to T*, we now get a cycle. Since e was defined to be the cheapest crossing edge, we can remove f from T* and we now have an MST of lower weight (removing an edge in a cycle doesn't affect connectedness). But this is a contradiction to the definition of T* meaning e must be in T*. | ||
Revision as of 21:29, 5 April 2016
group c
Contents
KRUSKAL
Kruskal's algorithm(similar to cheapest-link algorithm) is an algorithm used for computing the minimum spanning tree of a undirected edge-weighted graph.
Kruskal's algorithm works by choosing, on each iteration, the cheapest possible edge that does not create a cycle with edges already on the tree. Thus, generally, Kruskal's algorithm builds the MST by creating many disjoint trees that eventually coalesce into one spanning tree. For a visualization, see here (try the large graph to see how Kruskal creates disjoint trees along the way).
PRIM
The main alternative to Kruskal's algorithm for computing a minimum spanning tree is known as Prim's algorithm. Prim's algorithm computes the MST by adding edges to a single connected tree until all vertices have been included in the tree. In other words, start at an arbitrary vertex. Then add the cheapest edge that connects a vertex on the tree to a non-tree vertex. Repeat this procedure until V-1 edges have been added(a tree of a graph has exactly V-1 edges assuming the graph is connected). For a visualization of Prim's algorithm, see here.
For another example of Prim's algorithm:
G-C 3 E-D 8 D-H 6 I-D 1 J-E 15 I-E 11 G-F 16 H-G 13 I-H 12 J-I 9
Represented graphically as:
(A)------14-----(B)------2------(C)------10-----(D)------8------(E)
| /| /| /| /|
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
5 7 17 3 4 6 1 11 15
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
| / | / | / | / |
|/ |/ |/ |/ |
(F)------16-----(G)------13-----(H)------12-----(I)------9------(J)
If we start Prim's algorithm from G, the order in which edges are added to the MST (edge specified by weight) is :
3 2 4 6 1 7 5 8 9
Note that it is not necessary that edges are added from cheapest to most expensive, as is the case for Kruskal. Also, note how the edges added form one connected tree at each stage, which is not necessarily true of Kruskal.
CUT PROPERTY
A cut of a graph divides the vertices into two nonempty disjoint sets. A crossing edge of the cut is any edge that connects vertices in different sets.
The cut property states that given any cut in the graph, the cheapest crossing edge must be in the MST.
Proof: Assume distinct edge weights, although it is clear that if two edges are both the cheapest, either can be included. The proof is by contradiction. Define e to the cheapest crossing edge and let T* be the MST. Suppose T* does not contain e. Then T* must contain some other crossing edge f(since the MST is connected). If we add e to T*, we now get a cycle. Since e was defined to be the cheapest crossing edge, we can remove f from T* and we now have an MST of lower weight (removing an edge in a cycle doesn't affect connectedness). But this is a contradiction to the definition of T* meaning e must be in T*.
The reason Kruskal and Prim correctly compute the MST is due to the Cut Property. As outlined in the procedure for Prim above, at each stage Prim looks at the set of edges connecting tree vertices to non-tree vertices(i.e crossing edges). Prim then selects the cheapest crossing edge which, by the Cut Property, must be in the MST. After V-1 iterations, Prim has selected V-1 edges that all belong to the MST. Since there are exactly V-1 edges in the MST, Prim must have computed the MST.
RUNNING TIME
Depending on the implementation, Prim can run in time O(ElogE) or O(ElogV). Both implementations use a minimum priority queue to support the operations of finding the minimum crossing edge. However, the logE version is known as "lazy" Prim since it allows edges no longer eligible to be added to the tree to remain on the priority queue. The logV version is known as "eager" Prim, and stores only eligible edges on the priority queue.
