Prim’s Algorithm

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:

PRIMS MCST(G, w)
/* 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