Graphs are heavily used in real-life scenarios such as finding the shortest distance between two places on Google Maps, finding the nearest cab on Uber, and maintaining the user-friendly network on social networking sites like Facebook and LinkedIn. Software engineers use graphs in almost every aspect of their work, such as parsing a web page or understanding the DOM (document object model) structure, or implementing storage systems like GraphQL.

It’s no surprise that FAANG and other top tech companies often use graph-related questions to assess candidates for software engineering or software developer roles. If you’re preparing for your next tech interview, it is very important to learn graph-related concepts.

In this article, we’ll focus on Prim’s spanning tree algorithm:

• What is a minimum spanning tree?
• What Is Prims’s minimum spanning tree algorithm?
• How to find minimum spanning tree using Prim’s algorithm: Example
• How to implement the algorithm
• Time complexity of Prim’s algorithm
• FAANG interview questions on Prim’s algorithm
• FAQs on Prim’s algorithm
  

What Is a Minimum Spanning Tree?

A graph consists of some points and lines between them — it is a mathematical representation of a network that describes the relationship between the lines and points. A graph (G) is a set of vertices called nodes (v), which are connected by edges called links (e). 

Thus, G = (v, e).

A tree is an undirected graph in which any two vertices are connected by exactly one path (a connected acyclic undirected graph). A spanning tree is a subset of Graph G, which has all the vertices covered with a minimum possible number of edges. And if the graph is a weighted graph, the weight of the spanning tree will be the sum of the weights of edges in the tree. Among all the spanning trees, the one which has the minimum weight is called the minimum spanning tree (MST).

For example: If the graph is:

Some possible spanning trees are:

While the weights of the above spanning trees are 15 and 16 respectively, the minimum-weight spanning tree (minimum spanning tree) is 10.

What Is Prim’s Minimum Spanning Tree Algorithm?

Prim's algorithm is a greedy algorithm that finds the minimum spanning tree for a weighted undirected graph. The main idea behind this algorithm is that we want to take all the nodes of the graph and greedily connect them with minimum-weight edges. We start with an empty MST and keep track of two sets of nodes:

• In the first set, we’ll keep all the nodes added in the MST 
• In the second set, we’ll store all the nodes that are not added to the MST

Each time, we will take a node with minimum weight from the first set and traverse other nodes connected to that node. In the end, all the required nodes will in the first set, and that will be our MST.

Here are the steps of the algorithm:

1. Pick any random node of the graph. This node is to be used as the source node (src).
2. Initialize a boolean list visited, which will store true for all the nodes that are included in the MST.
3. Initialize a min_heap, which will store a pair of values in the form {weight, node}. Push {0, src} denotes that weight 0 is added to src node in the MST.
4. Initialize a weight list and initialize all indices with INFINITE. Set weight[src] = 0. This includes the minimum-weight edge that connects a node with a node in the visited set.
5. We will pick the minimum-weight node from the heap, add this node to the visited set, traverse its adjacent nodes, and:

• If the node is not in the visited set and the current edge’s weight is less than the weight that is currently at the adjacent node, then update the weight with the current edge’s weight and add this {edge_weight, node} pair to the heap.

1. Keep repeating Step 5 until all the nodes are not in the visited set.

How to Find Minimum Spanning Tree Using Prim's Algorithm: Example

Let’s consider the following graph:

Let’s say the random node is 1. Then initialize:

visited = [false, false, false, false, false]
min_heap = {{0, 1}}
weight = [0, inf, inf, inf, inf]

Note: List is 1-based indexing.

Step 1

Since the minimum-weight node that’s not visited is 1 (topmost value of the min_heap):

1. We will mark this node visited: visited = [true, false, false, false, false]

2. Next, we’ll remove the topmost value of min_heap. So, min_heap will become min_heap = {}

3. Next, we traverse to all the adjacent nodes of node 1:

• cur_node = 2, edge_weight = 5
  Since node 2 is not visited and edge_weight < weight[2], min_heap and weight list will become: min_heap = {{5, 2}} and weight = [0, 5, inf, inf, inf]
• cur_node = 3, edge_weight = 2
  Since node 3 is not visited and edge_weight < weight[3], min_heap and weight list will become: min_heap = {{2, 3}, {5, 2}} and weight = [0, 5, 2, inf, inf]

Step 2

The minimum-weight node that’s not visited is 3 (topmost value of the min_heap). In other words, the minimum weight among yellow nodes.

1. We will make this node visited: visited = [true, false, true, false, false]

2. Now, we’ll remove the topmost value of min_heap. So, min_heap = {{5, 2}}

3. Next, we traverse to all the adjacent nodes of node 3:

• cur_node = 4, edge_weight = 6
  Since node 4 is not visited and edge_weight < weight[4], min_heap = {{5, 2}, {6, 4}} and weight = [0, 5, 2, 6, inf]
• cur_node = 2, edge_weight = 4
  Since node 2 is not visited and edge_weight < weight[2]. So, min_heap = {{4, 2}, {5, 2}, {6, 4}} and weight = [0, 4, 2, 6, inf]

Step 3

The minimum-weight node that’s unvisited is 2 (topmost value of the min_heap).

1. We will make this node visited: visited = [true, true, true, false, false]

2. Now, we will remove the topmost value of the min_heap. So, min_heap = {{5, 2}, {6, 4}}

3. Next, we traverse to all the adjacent nodes of the node 2:

• cur_node = 1, edge_weight = 5
  Since node 1 is already visited (green), there will be no change in min_heap or weight list
• cur_node = 3, edge_weight = 4
  Since node 3 is already visited (green), there will be no change in min_heap or weight list
• cur_node = 5, edge_weight = 1
  Since node 5 is not visited and edge_weight < weight[5], min_heap = {{1, 5}, {5, 2}, {6, 4}} and weight = [0, 4, 2, 6, 1]

Step 4

The minimum-weight node that’s unvisited is 5 (topmost value of the min_heap).

1. We will make this node visited: visited = [true, true, true, false, true]

2. Now, we remove the topmost value of the min_heap: min_heap = {{5, 2}, {6, 4}}

3. Next, we traverse to all the adjacent nodes of the node 5:

• cur_node = 2, edge_weight = 1
  Since node 2 is already visited (green), there will be no change in min_heap or weight list
• cur_node = 4, edge_weight = 3
  Since node 4 is not visited and edge_weight < weight[4], min_heap = {{3, 4}, {5, 2}. {6, 4}} and weight = [0, 4, 2, 3, 1]

Step 5

The minimum-weight node that is unvisited is 4 (topmost value of the min_heap):

1. We will make this node visited: visited = [true, true, true, true, true]

2. Now, remove the topmost value of the min_heap. So, min_heap = {{5, 2}, {6, 4}}

3. Next, we traverse to all the adjacent nodes of node 4:

• cur_node = 5, edge_weight = 3
  Since node 5 is already visited (green), there will be no change in min_heap or weight list.
• cur_node = 3, edge_weight = 6
  Since node 3 is already visited (green), there will be no change in min_heap or weight list.

Result: Now, all the nodes are visited. If we calculate the sum of the weight list, it comes to 10, which is the weight of the MST.

How to Implement the Prim’s Algorithm

We’ve implemented the algorithm in C++. Please use this as a reference to code in C, Java, or any other programming language of your choice.

#include <bits/stdc++.h>
using namespace std;
#define inf 2e9
const int N = 1e3 + 5;
vector<pair<int, int>> adj[N];

int weight[N];

pair<int, int> parent[N];

bool visited[N];

void add_edge(int u, int v, int w) {
  adj[u].push_back({v, w});
  adj[v].push_back({u, w});
}

int prims(int n) {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // min_heap

  for (int i = 1; i <= n; i++) {
      visited[i] = false;
      weight[i] = inf;
  }

  int src = 1;
  weight[src] = 0;
  pq.push({0, src});
  parent[src] = {src, 0};

  while (!pq.empty()) {
      src = pq.top().second;
      pq.pop();

      if (visited[src]) {
          // if node is already visited
          continue;
      }

      visited[src] = true;

      for (auto it : adj[src]) {
          int node = it.first;
          int edge_weight = it.second;

          if (!visited[node] && edge_weight < weight[node]) {
              weight[node] = edge_weight;
              parent[node] = {src, edge_weight};
              pq.push({edge_weight, node});
          }
      }
  }

  int mst_weight = 0;
  for (int i = 1; i <= n; i++) {
      mst_weight += weight[i];
  }
  return mst_weight;
}

int main() {

  int n = 5; // number of nodes

  add_edge(1, 2, 5);
  add_edge(1, 3, 2);
  add_edge(2, 3, 4);
  add_edge(2, 5, 1);
  add_edge(3, 4, 6);
  add_edge(5, 4, 3);
  int mst_weight = prims(n);
  cout << "Minimum Spanning Tree cost will be " << mst_weight << endl;
  cout << "Edges included in the MST are" << endl;
  for (int i = 1; i <= n; i++) {
      if (parent[i].first != i) {
          cout << i << " " << parent[i].first << " " << parent[i].second << endl;
      }
  }

  return 0;
}

Output:

Minimum Spanning Tree cost will be 10

Edges included in the MST are

2 3 4

3 1 2

4 5 3

5 2 1

Time Complexity of Prim’s Algorithm

Prim’s algorithm works on the principle of min-heap. Forming a min-heap for V vertices requires O(V log V) time. 

Finding the minimum spanning tree requires going through each connected vertex of the current vertex and updating the min-heap according to the minimum edge weight of the connected vertex. For each vertex, the size of the adjacency list can be E (undirected graph), where E is the number of edges. The update operation in min-heap requires O(log V) time. Therefore, the total time complexity of this operation will be O(E log V).

Hence, the total time complexity = O(V log V) + O(E log V) = O(E log V)

Prim’s Algorithm vs. Kruskal’s Algorithm

FAANG Interview Questions on Prims Spanning Tree

Question 1: You have to build inter-city roads for a state. Building a road between two cities costs some amount of money. You have to build roads such that the total amount spent on building connections between cities should be minimum.

Question 2: Given: An array of points representing integer coordinates of some points on a 2D plane, where points[i] = [xi, yi]. Cost of connecting two points = the Euclidean distance between the points. Find the minimum cost to connect all points (exactly one simple path between any two points).

FAQs on Prim’s Spanning Tree

Question 1. Can there be multiple MST for a graph? 

Answer: Yes, there can be multiple minimum spanning trees in a graph. Multiple MSTs in the same graph can be found when any of the below conditions is true:

• Two or more edges have the same weight.
• Some edges may have positive weights, and some have negative weights.
  

Question 2: Does Prim's algorithm run on a negative edge weight graph?

Answer: Yes, the concept of Prim’s algorithm works on positive as well as negative edge weight graphs. This algorithm checks for the minimum edge weight from the set of edges whose one end (node) is already included in the MST. It doesn’t matter if the weight is positive or negative; the algorithm is only interested in the minimum weight.

Fun fact: If we increase all the edge weights by a constant amount, the MST(s) will not change.

Ready to Nail Your Next Coding Interview?

Nailing tech interviews at FAANG and Tier-1 tech companies can be challenging even for seasoned software engineers. It requires a deep understanding of data structure and algorithms as well as systems design. 

If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

----------

Article contributed by Problem Setters Official