Prim's Algorithm - Finding the Minimum Spanning Tree

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

The shortest road is from Cto E, length 1.

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

The closest to either C, Eto 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

You have no rights to post comments