Kruskal's Algorithm
Kruskal's algorithm is a method of find the minimum spanning tree for a network. The network is separated completely into it's constituent arcs. Arcs are selected in order of magnitude, shortest first, and added to the tree, with the poviso that any arc added does not form a cycle.
It must be noted, that unlike in Prim's algorithm, the tree does not have to be connected at each stage.
Consider the network.
The dissociated network is
The shortest length is CE.
The next is CG. Adding this to the network gives
AB and EF are the next shortest, both length 4. It does not matter which one we add. I choose EF.
Now add AB.
Then BD.
Then AC.
Addition of any more arcs would result in the formation of a cycle, hence this is the minimum spanning tree. The total weight is 4+6+6+1+4+2=23.
