(Summary of Kruskal and Prim with visualizations) |
(Added Cut Property) |
||
| Line 2: | Line 2: | ||
== '''KRUSKAL''' == | == '''KRUSKAL''' == | ||
| − | Kruskal's algorithm( | + | Kruskal's algorithm(similar to cheapest-link algorithm) is an algorithm used for computing the [https://en.wikipedia.org/wiki/Minimum_spanning_tree 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 works by choosing, on each iteration, the cheapest possible edge that does not create a cycle with edges already on the tree. Thus, generally, | ||
| Line 47: | Line 47: | ||
3 2 4 6 1 7 5 8 9 | 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. | + | 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 [https://en.wikipedia.org/wiki/Cut_(graph_theory) 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. | ||
| + | |||
| + | |||
[[Category:MA279Spring2016Walther]] | [[Category:MA279Spring2016Walther]] | ||
Revision as of 20:21, 5 April 2016
group c
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.
