Prim's Algorithm

Explanation

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a weighted undirected graph. The MST is a subset of the edges forming a tree that connects all vertices with the minimum possible total edge weight.

Steps of Prim's Algorithm:

1. Initialize a priority queue and a set to track visited nodes.
2. Start from any node and add its edges to the queue.
3. Repeat the following until all nodes are visited:
   • Extract the smallest edge from the queue.
   • If the destination node is not visited, add it to the MST and push its edges to the queue.

Time Complexity:

• Using Min-Heap and Adjacency List: O(E log V), where E = number of edges, V = number of vertices.

Space Complexity:

• O(V + E) for storing the graph and the priority queue.

Easy Problems

Problem 1: Minimum Cost to Connect All Points (Simplified Graph)

/* C++ Code */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int primSimple(vector<vector<pair<int, int>>>& graph, int n) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<bool> visited(n, false);
    int total = 0;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [cost, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        total += cost;

        for (auto [v, w] : graph[u])
            if (!visited[v]) pq.push({w, v});
    }
    return total;
}

Problem 2: Build Roads Between Cities

Given cities and road costs, connect all cities with minimum total cost.

/* Graph input same as above, call primSimple(graph, n) */

Intermediate Problems

Problem 1: Design Network with Redundancy

Find the MST and then analyze second-best MST for backup routes.

// Use Prim's to get MST, then test MST - e + e' for each non-MST edge.

Problem 2: Island Connection

Each island connected via bridges of given costs; connect all with min total cost.

// Similar to primSimple, graph built with input bridge costs.

Hard Problem

Problem: Optimize Power Grid

Connect a set of power stations and cities at minimal cost, with special discount rules.

/* Advanced Prim's with modified edge weights based on discount rules */

Conclusion

Prim's algorithm is essential for solving MST-related problems efficiently. Its greedy nature ensures optimal results in connecting nodes with minimal total cost.