Prim’s Algorithm

        It’s a greedy style algorithm and it’s guaranteed to produce a correct result.
In the following discussion, let the distance from each node not in the tree to the tree be the edge of minimal weight between that node and some node in the tree. If there is no such edge, assume the distance is infinity (this shouldn’t happen).
The algorithm (greedily) builds the minimal spanning tree by iteratively adding nodes into a working tree:

1. Start with a tree which contains only one node.
2. Identify a node (outside the tree) which is closest to the tree and add the minimum weight edge from that node to some node in the tree and incorporate the additional node as a part of the tree.
3. If there are less then n – 1 edges in the tree, go to 2

For the example graph, here’s how it would run:
Start with only node A in the tree.
          

Find the closest node to the tree, and add it.

Repeat until there are n – 1 edges in the tree.

 

That all the nodes are visited with minimum value .

Facebook Blogger Plugin by Pradeesh | Techie Touch