Prim’s Algorithm — Blog Analysis
Why is it used?
The main objective of this method is to find the minimum cost spanning tree.
(Spanning tree — If number of vertex = ‘v’, then number of edges = ‘v-1’)
So our task is to make this spanning tree, but the catch in Prim’s algorithm is that the cost should be the bare minimum.
Prelude —
Before understanding Prim’s Algorithm, we need to understand a few other concepts first.
Spanning Tree — A spanning tree can be defined as the subgraph of an undirected connected graph. It includes all the vertices along with the least possible number of edges. A spanning tree is a subset of the graph that does not have cycles, and it also cannot be disconnected. It consists of (n-1) edges, where ’n’ is the number of vertices (or nodes).
Minimum Spanning tree — Minimum spanning tree can be defined as the spanning tree in which the sum of the weights of the edge is minimum. The weight of the spanning tree is the sum of the weights given to the edges of the spanning tree.
Greedy Algorithm — An algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
Main Topic —
Prim’s Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a graph. Prim’s algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.
Prim’s algorithm starts with the single node (the beauty of the algorithm is that we can start from any node of our choice and we will still get the same final result) and explores all the adjacent nodes with all the connecting edges at every step. The edges with the minimal weights causing no cycles in the graph get selected.
The steps to implement the prim’s algorithm are as follows -
- First, we have to initialize a Minimum Spanning Tree (MST) with a randomly chosen vertex. (based on user’s choice)
- Now, we have to find all the edges that connect the tree in the above step with the new vertices. From the edges found, select the minimum edge and add it to the tree keeping in mind that no loops should be formed along the way.
- Repeat step 2 until the minimum spanning tree is formed.
Some applications of Prim’s Algorithm are -
- Prim’s algorithm can be used in network designing.
- It can be used to make network cycles.
- It can be used to lay down electrical wiring cables.
Working —
- We can start from any vertex. For example, start from vertex ‘b’ at leftmost side.
- Options are for vertex ‘a’ and ‘c’. We choose vertex ‘a’ since it has minimum cost out of the two. Cost of 1.
- At ‘a’ we again check. We can go to vertex ‘c’ with cost 6 or ‘d’ with cost 5. We choose vertex ‘d’.
- At vertex ‘d’ we choose the path ‘d’-’f’ since it has minimum cost of 2.
- At vertex ‘f’, we have vertex ‘h’ with cost 8 and vertex ‘c’ with cost 3. We choose vertex ‘c’.
- Now, at vertex ‘c’ a special case happens.
We have following options :-
- Vertex ‘b’-’c’ with cost 6 (Cannot consider since it will form a loop and spanning trees don’t have a loop)
- Vertex ‘a’-’c’ with cost 6 (Cannot consider since it will form a loop and spanning trees don’t have a loop)
- Vertex ‘d’-’g’ with cost 10 (Cannot consider since cost very high)
- Vertex ‘f’-’h’ with cost 8 (Cannot consider since cost very high)
- Vertex ‘c’-’e’ with cost 7 - Hence, despite minimum cost being 6, we choose vertex ‘e’ with cost 7 since it will satisfy the “no loop” criteria and is the minimum cost that can be considered too.
- At vertex ‘e’, we have following options :-
- Vertex ‘d’-’g’ with cost 10 (Cannot consider since cost very high)
- Vertex ‘f’-’h’ with cost 8
- Vertex ‘e’-’h’ with cost 12 (Cannot consider since cost very high)
Hence, we choose path from vertex ‘f’-’h’ with cost 8. - At vertex ‘h’ we choose path ‘h’-’g’ with cost 7 and finally from vertex ‘g’ we choose path ‘g’-’i’ with cost 3, which is minimum for both our cases.
And this gives us our final minimum spanning tree.
Complexity —
The running time of the prim’s algorithm depends upon using the data structure for the graph and the ordering of edges.
Analyze the table below -
Prim’s algorithm can be simply implemented by using the adjacency matrix or adjacency list graph representation, and to add the edge with the minimum weight requires the linearly searching of an array of weights.
It requires O(|V|2) running time. It can be improved further by using the implementation of heap to find the minimum weight edges in the inner loop of the algorithm.
To sum up, the time complexity of the prim’s algorithm is O(E logV) or
O(V logV), where E is the no. of edges, and V is the no. of vertices.
Advantages & Disadvantages —
Advantages of Prim’s Algorithm -
- It’s time complexity is better than Kruskal’s algorithm.
- It is helpful when dealing with dense graphs that have lots of edges.
- Beauty of algorithm is that we can start finding minimum spanning tree from any node of our choice, without any restriction.
Disadvantages of Prim’s Algorithm -
- Prim’s algorithm doesn’t allow us much control over the chosen edges when multiple edges with the same weight occur.
- Unlike Kruskal’s algorithm, Prim’s algorithm is a little harder to implement.
- Difficult to program, although it can be programmed in Matrix form.
- Prim’s algorithm requires the graph to be connected.
Kruskal, on the other hand, works on disjoint-set data structure, so it functions with disconnected graph as well.
Conclusion —
Prim’s Algorithm takes a greedy approach at finding a Minimum Spanning Tree (MSP) and works on only undirected connected graphs and is also a little difficult to implement while coding.
But despite these shortcomings, it has the best time complexity at finding an MSP and is fairly neat and structured in it’s approach when implementing physically on paper.
Overall, it is an excellent algorithm that initially requires a little effort to understand, but is a very powerful tool at finding an MSP in the most efficient and effective way.