Kruskal’s Algorithm

It's only fair to share...Share on FacebookTweet about this on TwitterPin on PinterestShare on Google+Share on RedditEmail this to someone

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.

Comments are closed.