Prim's Algorithm

By Priyanshu Vaish|Updated : August 26th, 2022

Prim's Algorithm is developed to discover a graph's minimum spanning tree. The algorithm is popular and follows different steps to solve the same problem. The prim’s algorithm selects the root vertex initially and then traverses from vertex to vertex adjacently.

Prim's algorithm is widely used as a Greedy algorithm that helps discover the most miniature spanning tree for a weighted undirected graph. This algorithm tends to search the subgroup of the edges that can construct a tree, and the complete poundage of all the edges in the tree should be minimal. Here, we will discuss what is Prim's algorithm along with its pseudocode, algorithm, and other essential details.

Download Formulas for GATE Computer Science Engineering - Programming & Data Structures

Table of Content

What is Prim's Algorithm?

Prim's algorithm has the property that the edges in the set T, which contains the edges of the minimum spanning tree when the algorithm proceeds step-by-step, always form a single tree. That is, at each step, there is only one connected component.

Prim's Algorithm Steps

The following steps are as follows:

  • Begin with one starting vertex (say v) of a given graph G(V, E).
  • Then, choose a minimum weight edge (u, v) connecting vertex v in set A to the vertices in the set (V-A) in each iteration. We always find an edge (u, v) of minimum weight, such as v ∈ A and u ∈ V-A. Then we modify the set A by adding u, A ← A ∪ {u}.
  • The process is repeated until ≠V, that is, until all the vertices are not in the set A.

Download Formulas for GATE Computer Science Engineering - Discrete Mathematics

Pseudocode of Prim's Algorithm

The pseudocode for prim's algorithm shows how we create two sets of vertices U and V-U. U contains the list of vertices that have been visited, and V-U is the list of vertices that haven't. One by one, we move vertices from set V-U to set U by connecting the least weight edge. The following pseudocode is used to construct the MCST(minimum cost spanning tree), using prim's algorithm that is as follows:

/* Input: An undirected connected weighted graph G = (V, E).
/* Output: A minimum cost spanning tree T(V, E') of G
Т ← ф // T contains the edges of the MST
A ← (Any arbitrary member of V)
while (A≠V)
find an edge (u, v) of minimum weight such that u ∈ V - A and v ∈ A
A ← A U {(u, v)}
B ← B U(u)

return T

Download Formulas for GATE Computer Science Engineering - Algorithms

Working on Prim's Algorithm

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 and explores all the adjacent nodes with all the connecting edges at every step. The working of prim's algorithm is as follows:

  1. Initially, the set A of nodes contains a single arbitrary node (starting vertex), and the set T of edges are empty.
  2. Prim's algorithm searches for the shortest possible edge (u, v) at each step such that u ∈ V-A and V ∈
  3. In this way, the edges in T form a minimal spanning tree for the nodes in A. Repeat this process until A ≠ V.

Analysis of Prim's Algorithm (By using min-heap)

Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The analysis of prim's algorithm by using min-heap is as follows.

For constructing heap: O(V)

The loop executes |V| times, and extracting the minimum element from the min-heap takes log V time, so while loop takes VlogV.
Total 'E' decrease key operations. Hence takes E log V
(Vlog V+E log V) = (V+ E) log V ≈ Elog V

Time Complexity of Prim's Algorithm

Assume we are given V vertices and E edges in a graph and need to find an MST. To complete one iteration, we delete the min node from the Min-Heap and add several edge weights to the Min-Heap.

We delete the V vertex from the Min-Heap because we have V vertices in the graph, and each iteration deletes 1 edge, for a total of V-1 edges in MST, with a complexity of O(log(V)). And we add up to E edges altogether, with each addition having a complexity of O(log(V)). As a result, the total complexity is O((V+E)Log(V)).

  • Using Fibonacci heap
    The prim's algorithm time complexity using the Fibonacci heap is O(E + V log V).
  • Using binomial heap
    The prim's algorithm time complexity using the binomial heap is O(V + E).
Important Topics for Gate Exam
Responsivity Types Of Governors
SR Flip-FlopTypes Of Vibration
Norton's TheoremWelded Joints
P N Junction DiodeRound Robin Scheduling
Classless AddressingScaling In Computer Graphics


write a comment

FAQs on Prim's Algorithms

  • The time complexity of the Prim's Algorithm is O ( (V + E)log V ) because each vertex is inserted in the priority queue only once, and insertion in the priority queue takes logarithmic time.

  • The advantage of Prim's algorithm is its complexity, which is better than Kruskal's algorithm. Therefore, Prim's algorithm is helpful when dealing with dense graphs that have lots of edges. However, Prim's algorithm doesn't allow us much control over the chosen edges when multiple edges with the same weight occur.

  • The time complexity of Kruskal's algorithm is O(E log V). In Prim's algorithm, all the graph elements must be connected. As a result, Kruskal's algorithm may have disconnected graphs. However, Prim's algorithm runs faster when it comes to dense graphs.

  • Prim's algorithm works efficiently if we keep a list d[v] of the cheapest weights, which connect a vertex, v, which is not in the tree, to any vertex already in the tree. Then, a second list pi[v] keeps the node's index already in the tree to which v can be connected with cost, d[v].

  • The list of edges has to be searched from the beginning as a new edge gets added. If more than one edge has the same weight, all possible spanning trees are required to be found for the final minimal tree.

Follow us for latest updates