Prims Algorithm

Also known as Jarniks algorithm is a type of greedy algorithm that is used for finding minimum spanning tree of weighted undirected graphs. It was developed by Vojtech Jarnik and was republished by Robert C. Prim in the year 1957.

How Prims algorithm works

Initially we start from 1 vertex that is either given or it is selected. From this vertex (let us say A) we check out other vertexes that are directly connected to this present vertex. We take the edge other than the present one which has the least weight (let it be towards the vertex B). Now we do the same process at the new vertex (B). Now we have to check whether the vertexes that we have selected are not in cyclic order. Assuming the next vertex that we have selected after B is vertex C then the vertex C should not be connected to the vertex A. Which can be deduced that the order in which the vertexes are connected should not form a closed loop or should not be in cyclic order. And if a closed loop is being formed then we will not select the node. We will continue all this till all the nodes are selected and a kind of tree is formed.

We can calculate the weight of the minimum spanning tree by adding weight of all the edges of the minimum spanning.

Prims Algorithm time complexity: it has a time complexity of O(V2) using adjacency matrix, but can be improved to O (V+V Log V + E) using Fibonacci heap.

Example:

Taking the example of this grid:

First of all, let’s say that due to some constraints you have to start the spanning tree from the node (a).

Now from the node (A) checking which node has lesser weight, we select the edge (AB) having weight 2. Now from the vertex (B) be check and reach to Node (D). But, if by any chance the scenario come out to be like we are on vertex © then we can not select the Vertex (A) again as then a cyclic tree will get formed. Continuing from the node (D) we have to complete the tree. If needed we can come back to any of the traversed nodes to make a subbranch. After Completion the spanning tree we will get will look as the figure given below:

For the calculation of the weight of this spanning tree

Weight = (AC) + (AB) + (BD) + (DE) + (DF)

ð 3 + 2 + 3 + 2 + 3

ð 13

There fore this is the minimum spanning tree.

Advantages

Prim’s algorithm can be used in various fields in today’s world such as designing a road network to link g small outlying villages, setting up a network of pipeline of drinking water or natural gas, making charts of electrical grid, irrigation channels, a fiber-optic grid, placing microwave towers, or similar projects.

Failure of Prim’s: Prim’s algorithm assumes that all vertices are connected. But in a directed graph, every node is not reachable from every other node.