Prim’s Algorithm – Finding the Minimum Spanning Tree

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

We apply this algorithm to assemble a “minimum spanning tree”. Suppose we have a network of roads, where each road connects two town. Some of the roads may be redundant, in that for any two towns, you could go from one town to the other by two different routes, in which case one of the routes may be discarded. The algorithm discards all the redundant routes so that in the end any town can be reach from any other, and the lengths of all the roads add up to the smallest possible number. We select the rods in order of their length, such that the next length added is connects a town closest to any already town already in our semi assembled network.

The shortest road is from C to E, length 1.

The closest to either C or E is G and the length from C to G is 2.

The closest to either C, E to G is F and the length from E to F is 4.

The next closest is A, distance 5 from C.

Then B, 4 from A.

Then D, 6 from B.

The total length of the minimum tree us 1+2+4+4+5+6=22

Comments are closed.