Prim’s Algorithm

By BYJU'S Exam Prep

Updated on: September 25th, 2023

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

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-Flop Types Of Vibration
Norton’s Theorem Welded Joints
P N Junction Diode Round Robin Scheduling
Classless Addressing Scaling In Computer Graphics
Our Apps Playstore
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303
Home Practice Test Series Premium