Prim's Algorithm | Working, Analysis

By Priyanshu Vaish|Updated : May 23rd, 2022

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

Prim's algorithm is popular as a greedy algorithm that helps discover the smallest 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.

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. 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. That is, we always find an edge (u, v) of minimum weight such that v ∈ A and u ∈ V-A. Then we modify the set A by adding u, which is A ← A ∪ {u}.
  • The process is repeated until ≠V, that is until all the vertices are not in the set A.

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
}

Working of 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 (that is, 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 at any instance 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
Using Fibonacci heap
The time complexity of prim's algorithm is O(E + V log V)
Using binomial heap
The time complexity of prim's algorithm is O(V + E)

Comments

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