Prim’s Algorithm

Description

Prim’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, undirected graph. It starts with a single vertex and grows the MST one edge at a time by adding the smallest edge that connects a vertex in the MST to a vertex outside the MST.

C++ Code

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

typedef pair<int, int> iPair;

void primMST(vector<vector<iPair>>& graph, int V) {
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
    int src = 0;

    vector<int> key(V, INT_MAX);
    vector<int> parent(V, -1);
    vector<bool> inMST(V, false);

    pq.push(make_pair(0, src));
    key[src] = 0;

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

        inMST[u] = true;

        for (auto x : graph[u]) {
            int v = x.first;
            int weight = x.second;

            if (!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push(make_pair(key[v], v));
                parent[v] = u;
            }
        }
    }

    for (int i = 1; i < V; ++i)
        cout << parent[i] << " - " << i << endl;
}

int main() {
    int V = 9;
    vector<vector<iPair>> graph(V);

    graph[0].push_back(make_pair(1, 4));
    graph[0].push_back(make_pair(7, 8));
    graph[1].push_back(make_pair(0, 4));
    graph[1].push_back(make_pair(2, 8));
    graph[1].push_back(make_pair(7, 11));
    graph[2].push_back(make_pair(1, 8));
    graph[2].push_back(make_pair(3, 7));
    graph[2].push_back(make_pair(5, 4));
    graph[2].push_back(make_pair(8, 2));
    graph[3].push_back(make_pair(2, 7));
    graph[3].push_back(make_pair(4, 9));
    graph[3].push_back(make_pair(5, 14));
    graph[4].push_back(make_pair(3, 9));
    graph[4].push_back(make_pair(5, 10));
    graph[5].push_back(make_pair(2, 4));
    graph[5].push_back(make_pair(3, 14));
    graph[5].push_back(make_pair(4, 10));
    graph[5].push_back(make_pair(6, 2));
    graph[6].push_back(make_pair(5, 2));
    graph[6].push_back(make_pair(7, 1));
    graph[6].push_back(make_pair(8, 6));
    graph[7].push_back(make_pair(0, 8));
    graph[7].push_back(make_pair(1, 11));
    graph[7].push_back(make_pair(6, 1));
    graph[7].push_back(make_pair(8, 7));
    graph[8].push_back(make_pair(2, 2));
    graph[8].push_back(make_pair(6, 6));
    graph[8].push_back(make_pair(7, 7));

    primMST(graph, V);

    return 0;
}

2. Time and Space Complexity Analysis in Table Format

```markdown

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Prim’s Algorithm	O(E log V)	O(V + E)

Where:

• V: Number of vertices.
• E: Number of edges.

← Back to Homepage