(Created page with "group c") |
(Summary of Kruskal and Prim with visualizations) |
||
| Line 1: | Line 1: | ||
group c | group c | ||
| + | |||
| + | == '''KRUSKAL''' == | ||
| + | Kruskal's algorithm(also known as 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 builds the MST by creating many disjoint trees that eventually coalesce into one spanning tree. For a visualization, [https://www.cs.usfca.edu/~galles/visualization/Kruskal.html 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, [https://upload.wikimedia.org/wikipedia/en/3/33/Prim-algorithm-animation-2.gif 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. | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | [[Category:MA279Spring2016Walther]] | ||
Revision as of 19:55, 5 April 2016
group c
KRUSKAL
Kruskal's algorithm(also known as 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.
