PRIM’S ALGORITHM
PRIM’S ALGORITHM Prim’s algorithm is a greedy algorithm that is used to find a minimum spanning tree (MST) of a given connected weighted graph. This algorithm is preferred when the graph is dense. The dense graph is a graph in which there is a large number of edges in the graph. This algorithm can be applied to only undirected connected graph and there should not be any negative weighted edge. In this case, the algorithm is quite efficient. Since there are no non-negative weight cycles, there will be a shortest path whenever there is a path. The steps to find minimum spanning tree using Prim’s algorithm are as follows: 1. If graph has loops and parallel edges than remove loops and parallel edges of that graph. 2. Randomly choose any node, labelling it with a distance of 0 and all other nodes as ∞. The chosen node is treated as current node and considered as visited. All other nodes are considered as unvisited....