🌟 Exploring Prim's Algorithm: A Beginner's Guide

Are you eager to learn about algorithms that solve graph theory problems? Today, let's delve into Prim's algorithm, a popular method for finding the minimum spanning tree (MST) of a weighted undirected graph. We'll break down the algorithm step-by-step, provide a C++ implementation, and recommend LeetCode problems to solidify your understanding.

🔍 Understanding Prim's Algorithm

Prim's algorithm aims to find the minimum spanning tree (MST) of a connected, undirected graph. The MST is a subset of edges that connect all vertices together without forming any cycles and has the minimum possible total edge weight. Here's how Prim's algorithm works:

1. Start with a single vertex: Initialize the MST with a single vertex.

2. Grow the MST: Add the nearest vertex not yet in the MST to the tree. Repeat this process until all vertices are included.

3. Choose the minimum edge: At each step, choose the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST.

4. Update distances: Update the distances from the vertices in the MST to the vertices outside the MST.

🖼️ Step-by-Step Process with Images

Step 1: Initialize MST
Step 2: Add Nearest Vertex
Step 3: Choose Minimum Edge
Step 4: Update Distances

🛠️ Implementation in C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9;

int primMST(vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    int cost = 0;
    pq.push({0, 0});
    dist[0] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;
        cost += w;

        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight;
                pq.push({dist[v], v});
            }
        }
    }
    return cost;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    int minimum_cost = primMST(graph);
    cout << "Minimum Cost of MST: " << minimum_cost << endl;
    return 0;
}

🔗 LeetCode Problems for Practice

1. Minimum Spanning Tree
2. Network Delay Time
3. Connecting Cities With Minimum Cost
4. Redundant Connection II
5. Cheapest Flights Within K Stops

Feel free to ask any questions or share your insights about Prim's algorithm in the comments! Let's explore and learn together. 🌟🚀