Prim's Minimum Spanning Tree Algorithm

Prim’s algorithm is a graph-based algorithm used to construct a Minimum Spanning Tree (MST) for a given weighted, undirected graph. It builds the MST by greedily selecting the lowest-weight edge that connects a vertex in the growing MST to a vertex outside it. Prim’s algorithm maintains a priority queue to efficiently select the next minimum-weight edge, ensuring that at each step, it chooses the cheapest way to expand the MST without creating cycles. This process continues until all vertices are included in the MST.

Prim’s algorithm is a greedy algorithm, meaning it always chooses the cheapest edge at each step, without considering the long-term consequences of its choices. Despite its simplicity, Prim’s algorithm is proven to be efficient and effective in finding the MST of a weighted, connected graph.

What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all the vertices together with the minimum possible total edge weight. In other words, it is the cheapest or minimum cost subgraph in a given graph that connects all the nodes in the graph.

For example, for the undirected weighted graph shown below:

Below is how the minimum spanning tree looks like:

Refer to this article to learn more about Minimum Spanning Trees.

Detailed Steps of Prim’s MST Algorithm

Prim’s algorithm builds the MST incrementally, starting with a single vertex and expanding the tree by adding the cheapest possible edge from the tree to a vertex not yet in the tree. It maintains a growing set of vertices that are part of the MST and continuously adds the smallest weight edge that connects a vertex in the MST to a vertex outside the MST.

Step-by-step process of Prim’s algorithm:

Initialization:
- Select an arbitrary vertex to start the MST. This vertex is the initial member of the MST set.
- Initialize a set to keep track of vertices included in the MST.
- Create an array to store the minimum cost edge that connects each vertex to the growing MST. Initialize the starting vertex’s cost to zero and others to infinity.
- Use a priority queue (or a min-heap) to store unused edges connected to the current MST.
Growing the MST:
- While the MST set does not contain all the vertices:
  - Select and remove the minimum-weight edge from the priority queue.
  - If the edge connects to a vertex already in the MST, discard it and continue.
  - Otherwise, add this edge to the MST and the new vertex to the MST set.
  - For each adjacent vertex of the extracted vertex, if the vertex is not yet in the MST, add the edge to priority queue.
Termination:
- The process continues until all vertices are included in the MST set.

The use of a priority queue allows for efficient selection of the minimum-weight edge at each step. If priority queue is not used, we would need to sort all edges every time a new edge is added.

Implementation


import heapq

# Function to find the minimum spanning tree
# Using Prim's Minimum Spanning Tree Algorithm
def prims_mst(graph, start_node):
  # Initialize a set to keep track of nodes
  # Which are already added to the MST
  visited = set()
  
  # Initialize a priority queue to store the edges
  pq = []
  
  # Initialize the total weight of the MST
  total_weight = 0
  
  # Initialize a list to store the edges in the MST
  mst_edges = []
  
  # Add the starting node to the visited set
  visited.add(start_node)
  
  # Add all the edges from the starting node to the priority queue
  for neighbor, weight in graph[start_node]:
    heapq.heappush(pq, (weight, start_node, neighbor))
  
  # While the priority queue is not empty
  while pq:
    # Pop the edge with the minimum weight from the priority queue
    weight, u, v = heapq.heappop(pq)
    
    # If the destination node has not been visited yet
    if v not in visited:
      # Add the edge to the MST
      mst_edges.append((u, v, weight))
      
      # Add the weight of the edge to the total weight
      total_weight += weight
      
      # Add the destination node to the visited set
      visited.add(v)
      
      # Add all the edges from the new node to the priority queue
      for neighbor, neighbor_weight in graph[v]:
        if neighbor not in visited:
          heapq.heappush(pq, (neighbor_weight, v, neighbor))
  
  # Return the total weight and the edges in the MST
  return mst_edges, total_weight

if __name__ == "__main__":
  # Graph represented as adjacency list
  graph = {
      "A": [("B", 8), ("D", 2), ("E", 4)],
      "B": [("A", 8), ("C", 7), ("F", 4)],
      "C": [("B", 7), ("D", 9), ("F", 6)],
      "D": [("A", 2), ("C", 9), ("E", 5)],
      "E": [("A", 4), ("D", 5), ("F", 3)],
      "F": [("B", 4), ("C", 6), ("E", 3)],
  }

  mst, total_weight = prims_mst(graph, "A")

  print("Minimum Spanning Tree edges:")
  for edge in mst:
    print(f"({edge[0]} - {edge[1]}) with weight {edge[2]}")
  print(f"Total weight of MST: {total_weight}")


#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

// Function to find the minimum spanning tree
// Using Prim's Minimum Spanning Tree Algorithm
vector<tuple<string, string, int>> prims_mst(unordered_map<string, vector<pair<string, int>>>& graph, string start_node) {
  // Initialize a set to keep track of nodes
  // Which are already added to the MST
  unordered_set<string> visited;

  // Initialize a priority queue to store the edges
  priority_queue<tuple<int, string, string>, vector<tuple<int, string, string>>, greater<tuple<int, string, string>>> pq;

  // Initialize a vector to store the edges in the MST
  vector<tuple<string, string, int>> mst_edges;

  // Add the starting node to the visited set
  visited.insert(start_node);

  // Add all the edges from the starting node to the priority queue
  for (auto neighbor : graph[start_node]) {
    pq.push(make_tuple(neighbor.second, start_node, neighbor.first));
  }

  // While the priority queue is not empty
  while (!pq.empty()) {
    // Pop the edge with the minimum weight from the priority queue
    int weight;
    string u, v;
    tie(weight, u, v) = pq.top();
    pq.pop();

    // If the destination node has not been visited yet
    if (visited.find(v) == visited.end()) {
      // Add the edge to the MST
      mst_edges.emplace_back(u, v, weight);

      // Add the destination node to the visited set
      visited.insert(v);

      // Add all the edges from the new node to the priority queue
      for (auto neighbor : graph[v]) {
        if (visited.find(neighbor.first) == visited.end()) {
          pq.push(make_tuple(neighbor.second, v, neighbor.first));
        }
      }
    }
  }

  return mst_edges;
}

int main() {
  // Graph represented as adjacency list
  unordered_map<string, vector<pair<string, int>>> graph = {
      {"A", {{"B", 8}, {"D", 2}, {"E", 4}}},
      {"B", {{"A", 8}, {"C", 7}, {"F", 4}}},
      {"C", {{"B", 7}, {"D", 9}, {"F", 6}}},
      {"D", {{"A", 2}, {"C", 9}, {"E", 5}}},
      {"E", {{"A", 4}, {"D", 5}, {"F", 3}}},
      {"F", {{"B", 4}, {"C", 6}, {"E", 3}}}
  };

  vector<tuple<string, string, int>> mst = prims_mst(graph, "A");

  int total_weight = 0;
  cout << "Minimum Spanning Tree edges:" << endl;
  for (auto edge : mst) {
    cout << "(" << get<0>(edge) << " - " << get<1>(edge) << ") with weight " << get<2>(edge) << endl;
    total_weight += get<2>(edge);
  }
  cout << "Total weight of MST: " << total_weight << endl;

  return 0;
}


// Function to find the minimum spanning tree
// Using Prim's Minimum Spanning Tree Algorithm
function primsMST(graph, startNode) {
  // Initialize a set to keep track of nodes
  // Which are already added to the MST
  const visited = new Set();

  // Initialize a priority queue to store the edges
  const pq = [];

  // Initialize the total weight of the MST
  let totalWeight = 0;

  // Initialize a list to store the edges in the MST
  const mstEdges = [];

  // Add the starting node to the visited set
  visited.add(startNode);

  // Add all the edges from the starting node to the priority queue
  for (const [neighbor, weight] of graph[startNode]) {
    pq.push([weight, startNode, neighbor]);
  }
  pq.sort((a, b) => a[0] - b[0]);

  // While the priority queue is not empty
  while (pq.length > 0) {
    // Pop the edge with the minimum weight from the priority queue
    const [weight, u, v] = pq.shift();

    // If the destination node has not been visited yet
    if (!visited.has(v)) {
      // Add the edge to the MST
      mstEdges.push([u, v, weight]);

      // Add the weight of the edge to the total weight
      totalWeight += weight;

      // Add the destination node to the visited set
      visited.add(v);

      // Add all the edges from the new node to the priority queue
      for (const [neighbor, neighborWeight] of graph[v]) {
        if (!visited.has(neighbor)) {
          pq.push([neighborWeight, v, neighbor]);
        }
      }
      pq.sort((a, b) => a[0] - b[0]);
    }
  }

  // Return the total weight and the edges in the MST
  return [mstEdges, totalWeight];
}

// Graph represented as adjacency list
const graph = {
  A: [["B", 8], ["D", 2], ["E", 4]],
  B: [["A", 8], ["C", 7], ["F", 4]],
  C: [["B", 7], ["D", 9], ["F", 6]],
  D: [["A", 2], ["C", 9], ["E", 5]],
  E: [["A", 4], ["D", 5], ["F", 3]],
  F: [["B", 4], ["C", 6], ["E", 3]],
};

const [mst, totalWeight] = primsMST(graph, "A");

console.log("Minimum Spanning Tree edges:");
for (const [u, v, weight] of mst) {
  console.log(`(${u} - ${v}) with weight ${weight}`);
}
console.log(`Total weight of MST: ${totalWeight}`);

Time and Space Complexity

Time Complexity:

The time complexity of Prim’s algorithm depends on how dense the graph is and the data structure used to store and retrieve available edges. The most common implementation uses a priority queue (e.g., a min-heap) to efficiently select the next vertex to add to the MST. With a priority queue, the time complexity of Prim’s algorithm is O(E log V), where E is the number of edges in the graph and V is the number of vertices in the graph.

This is because the algorithm needs to:

Inserting each vertex into the priority queue takes O(log V) per edge. Note: Although the heap/priority queue size can grow to V * V-1 if each node in the graph has a link to every other node in the graph, the heap operation takes O(log V^2) which is 2*O(log V) which in turn can be approximated to O(log V).
Similarly, extracting the minimum-weight vertex from the priority queue takes O(log V) per extraction

The algorithm performs these operations for a maximum of E times, resulting in the overall time complexity of O(E log V).

Space Complexity:

The space complexity of Prim’s algorithm is O(E + V), as the algorithm needs to store the following data structures:

A priority queue to keep track of the vertices and their weights which can take a maximum of O(V) space
A set or array to keep track of the vertices that have already been added to the MST which takes O(V) space

Therefore, the overall space complexity of Prim’s algorithm is O(E + V).