Minimum Spanning Tree - Prim

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Prim's algorithm using adjacency list and a min-heap (priority_queue with greater<>)
5
// This version uses lazy deletion: we may push multiple entries for a vertex,
6
// and we skip outdated ones using a visited[] array when they pop.
7
// It computes an MST if the graph is connected; otherwise it reports disconnection.
8
9
struct Edge { int to; long long w; };
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n, m; // n = number of vertices (0..n-1), m = number of edges
16
    if (!(cin >> n >> m)) return 0;
17
18
    vector<vector<Edge>> adj(n);
19
    for (int i = 0; i < m; ++i) {
20
        int u, v; long long w;
21
        cin >> u >> v >> w; // assume 0-based input; convert if needed
22
        if (u == v) continue; // ignore self-loops
23
        // For undirected graph, add both directions
24
        adj[u].push_back({v, w});
25
        adj[v].push_back({u, w});
26
    }
27
28
    const long long INF = (1LL<<62);
29
    vector<int> parent(n, -1);
30
    vector<char> visited(n, false);
31
32
    // min-heap of (weight, vertex, parent_of_vertex)
33
    using T = tuple<long long,int,int>;
34
    priority_queue<T, vector<T>, greater<T>> pq;
35
36
    // Start from vertex 0 by convention (can be any)
37
    pq.push({0LL, 0, -1});
38
39
    long long total = 0;
40
    vector<pair<int,int>> mst_edges; // store (u,v)
41
42
    while (!pq.empty() && (int)mst_edges.size() < n - 1) {
43
        auto [w, v, p] = pq.top(); pq.pop();
44
        if (visited[v]) continue; // lazy skip
45
        visited[v] = true;
46
        if (p != -1) {
47
            total += w; // add the chosen edge weight
48
            mst_edges.push_back({p, v});
49
        }
50
        // push candidate edges to neighbors
51
        for (const auto &e : adj[v]) {
52
            if (!visited[e.to]) {
53
                pq.push({e.w, e.to, v});
54
            }
55
        }
56
    }
57
58
    // Check connectivity: all vertices must be visited to have an MST
59
    bool connected = true;
60
    for (int v = 0; v < n; ++v) connected &= visited[v];
61
62
    if (!connected) {
63
        cout << "Graph is disconnected: no single MST exists.\n";
64
        return 0;
65
    }
66
67
    cout << "MST total weight = " << total << "\n";
68
    cout << "Edges (u v):\n";
69
    for (auto &e : mst_edges) cout << e.first << ' ' << e.second << '\n';
70
    return 0;
71
}
72

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Prim's algorithm using an adjacency matrix and arrays.
5
// Suitable for dense graphs where O(V^2) is acceptable or optimal.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int n, m; // vertices are 0..n-1
12
    if (!(cin >> n >> m)) return 0;
13
14
    const long long INF = (1LL<<62);
15
    vector<vector<long long>> G(n, vector<long long>(n, INF));
16
    for (int i = 0; i < n; ++i) G[i][i] = INF; // ignore self-loops
17
18
    for (int i = 0; i < m; ++i) {
19
        int u, v; long long w;
20
        cin >> u >> v >> w;
21
        if (u == v) continue;
22
        // Keep the smallest parallel edge
23
        G[u][v] = min(G[u][v], w);
24
        G[v][u] = min(G[v][u], w);
25
    }
26
27
    vector<long long> key(n, INF);
28
    vector<int> parent(n, -1);
29
    vector<char> inMST(n, false);
30
31
    // Start from vertex 0
32
    key[0] = 0;
33
34
    for (int iter = 0; iter < n; ++iter) {
35
        // pick u with minimal key not yet in MST
36
        int u = -1;
37
        for (int v = 0; v < n; ++v) {
38
            if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;
39
        }
40
        if (u == -1 || key[u] == INF) {
41
            cout << "Graph is disconnected: no single MST exists.\n";
42
            return 0;
43
        }
44
        inMST[u] = true;
45
        // relax neighbors via matrix row
46
        for (int v = 0; v < n; ++v) {
47
            if (!inMST[v] && G[u][v] < key[v]) {
48
                key[v] = G[u][v];
49
                parent[v] = u;
50
            }
51
        }
52
    }
53
54
    long long total = 0;
55
    for (int v = 0; v < n; ++v) total += (parent[v] == -1 ? 0 : key[v]);
56
57
    cout << "MST total weight = " << total << "\n";
58
    cout << "Edges (u v):\n";
59
    for (int v = 0; v < n; ++v) if (parent[v] != -1) cout << parent[v] << ' ' << v << '\n';
60
    return 0;
61
}
62

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Prim's algorithm using std::set to emulate decrease-key.
5
// This version restarts from each unvisited vertex to build a minimum spanning forest (MSF)
6
// if the graph is disconnected.
7
8
struct Edge { int to; long long w; };
9
10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    int n, m; // 0..n-1 vertices
15
    if (!(cin >> n >> m)) return 0;
16
17
    vector<vector<Edge>> adj(n);
18
    for (int i = 0; i < m; ++i) {
19
        int u, v; long long w; cin >> u >> v >> w;
20
        if (u == v) continue; // ignore self-loops
21
        adj[u].push_back({v, w});
22
        adj[v].push_back({u, w});
23
    }
24
25
    const long long INF = (1LL<<62);
26
    vector<long long> key(n, INF);
27
    vector<int> parent(n, -1);
28
    vector<char> inMST(n, false);
29
30
    long long total = 0;
31
    vector<pair<int,int>> forest_edges;
32
33
    for (int start = 0; start < n; ++start) {
34
        if (inMST[start]) continue;
35
        // Initialize a set of (key, vertex) for this component
36
        set<pair<long long,int>> pq;
37
        key[start] = 0;
38
        parent[start] = -1;
39
        pq.insert({0, start});
40
        while (!pq.empty()) {
41
            auto [kv, u] = *pq.begin();
42
            pq.erase(pq.begin());
43
            if (inMST[u]) continue; // may occur if key improved and old pair remained
44
            inMST[u] = true;
45
            if (parent[u] != -1) {
46
                total += key[u];
47
                forest_edges.push_back({parent[u], u});
48
            }
49
            for (auto &e : adj[u]) {
50
                int v = e.to; long long w = e.w;
51
                if (!inMST[v] && w < key[v]) {
52
                    // decrease-key: remove old pair if present, insert new one
53
                    if (key[v] != INF) pq.erase({key[v], v});
54
                    key[v] = w;
55
                    parent[v] = u;
56
                    pq.insert({key[v], v});
57
                }
58
            }
59
        }
60
    }
61
62
    cout << "Minimum Spanning Forest total weight = " << total << "\n";
63
    cout << "Edges (u v):\n";
64
    for (auto &e : forest_edges) cout << e.first << ' ' << e.second << '\n';
65
    return 0;
66
}
67