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.
