šŸ“” Prim's Algorithm ā€“ Complete In-Depth Explanation

Prim's Algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) for a weighted, undirected graph. An MST connects all vertices in a graph without cycles and with the minimum total edge weight.

šŸ“Œ Why is Prim's Algorithm Important?

  • āš™ļø Fundamental algorithm for network design.
  • šŸ’” Efficiently finds the cheapest way to connect all nodes.
  • šŸš€ Used in various applications, from telecommunications to circuit design.

šŸ“Œ Understanding Prim's Algorithm with an Example

Let's consider a simple graph: 


                    2    3
                A --- B --- C
                |    |    |
                1    4    6
                |    |    |
                D --- E --- F
                    5

Prim's Algorithm starts at an arbitrary vertex (e.g., A) and iteratively adds the edge with the smallest weight that connects a vertex in the MST to a vertex not yet in the MST. Here's a step-by-step visualization:

  1. Start with A: Add A to the MST.
  2. Smallest edge from A: Edge A-D (weight 1). Add D to the MST.
  3. Smallest edge from A or D: Edge A-B (weight 2). Add B to the MST.
  4. Smallest edge from A, B, or D: Edge B-C (weight 3). Add C to the MST.
  5. Smallest edge from A, B, C, or D: Edge D-E (weight 5). Add E to the MST.
  6. Smallest edge from A, B, C, D, or E: Edge C-F (weight 6). Add F to the MST.

The resulting MST is: 


                    2    3
                A --- B --- C
                |        |
                1        6
                |        |
                D --- E   F
                    5

šŸ”¹ Key Points

  • Starts from an arbitrary vertex.
  • Greedily selects the minimum-weight edge connecting the MST to a new vertex.
  • Guarantees finding the MST.

šŸ›  Solution Approaches

Prim's Algorithm can be implemented in a few ways, with different time complexities:

šŸ“Œ 1. Using an Adjacency Matrix (O(VĀ²))

This approach is simpler to implement but less efficient for sparse graphs (graphs with few edges).

šŸ“Œ 2. Using a Priority Queue (O(E log V))

This approach is more efficient, especially for sparse graphs. It uses a priority queue to keep track of the smallest edges. 


                  #include 
                  #include 
                  #include 
                  #include 
              
                  using namespace std;
              
                  void primMST(vector>>& adj, int V) {
                      priority_queue, vector>, greater>> pq;
                      vector key(V, INT_MAX); // Stores min edge weight to connect to MST
                      vector parent(V, -1);    // Stores parent node in MST
                      vector inMST(V, false);   // Tracks vertices already in MST
              
                      pq.push({0, 0}); // {weight, vertex} - Start with vertex 0 and weight 0
                      key[0] = 0;
              
                      for (int count = 0; count < V - 1; count++) {
                          int u = pq.top().second;
                          pq.pop();
                          inMST[u] = true;
              
                          for (auto& edge : adj[u]) {
                              int v = edge.first;
                              int weight = edge.second;
              
                              if (inMST[v] == false && weight < key[v]) {
                                  parent[v] = u;
                                  key[v] = weight;
                                  pq.push({key[v], v});
                              }
                          }
                      }
              
                      cout << "Edge \tWeight\n";
                      for (int i = 1; i < V; i++)
                          cout << parent[i] << " - " << i << "\t" << key[i] << "\n";
                  }
              
                  int main() {
                      int V = 6;
                      vector>> adj(V);
              
                      // Add edges (example graph)
                      adj[0].push_back({1, 2}); adj[1].push_back({0, 2});
                      adj[0].push_back({3, 1}); adj[3].push_back({0, 1});
                      adj[1].push_back({2, 3}); adj[2].push_back({1, 3});
                      adj[3].push_back({4, 5}); adj[4].push_back({3, 5});
                      adj[1].push_back({4,4}); adj[4].push_back({1,4});
                      adj[2].push_back({5, 6}); adj[5].push_back({2, 6});
              
                      primMST(adj, V);
              
                      return 0;
                  }

ā³ Time Complexity Analysis

Using a priority queue, Prim's Algorithm has a time complexity of O(E log V), where E is the number of edges and V is the number of vertices.

šŸŒ Real-World Applications of Prim's Algorithm

  • šŸ“” Network design (telecommunications, computer networks).
  • šŸ”Œ Designing efficient electrical grids.
  • šŸ—ŗ Road network planning.

šŸ”— Next Topics