PRIM

#include <bits/stdc++.h>  // Thư viện tiêu chuẩn cho C++ (bao gồm tất cả các thư viện phổ biến)
using namespace std;

void primMST(int V, vector<vector<pair<int, int>>>& adj) {  // Hàm tìm MST với V đỉnh và danh sách kề 'adj'
    vector<int> key(V, INT_MAX), parent(V, -1);  // 'key' lưu trọng số nhỏ nhất để kết nối, 'parent' lưu đỉnh cha
    vector<bool> inMST(V, false);  // Đánh dấu đỉnh nào đã được thêm vào MST
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // Min-heap lưu (trọng số, đỉnh)

    key[0] = 0;  // Khởi tạo đỉnh đầu tiên với trọng số 0 (bắt đầu từ đỉnh 0)
    pq.push({0, 0});  // Đẩy đỉnh 0 vào hàng đợi ưu tiên với trọng số 0

    while (!pq.empty()) {  // Vòng lặp chính: Chạy cho đến khi hàng đợi rỗng
        int u = pq.top().second;  // Lấy đỉnh 'u' có trọng số nhỏ nhất từ hàng đợi
        pq.pop();  // Loại bỏ đỉnh 'u' khỏi hàng đợi
        inMST[u] = true;  // Đánh dấu 'u' đã được thêm vào MST

        // Duyệt qua tất cả các đỉnh kề 'v' của 'u' với trọng số 'weight'
        for (auto& [v, weight] : adj[u]) {  
            // Nếu 'v' chưa thuộc MST và 'weight' nhỏ hơn trọng số hiện tại 'key[v]'
            if (!inMST[v] && weight < key[v]) {  
                key[v] = weight;  // Cập nhật 'key[v]' với trọng số mới
                pq.push({key[v], v});  // Đẩy (trọng số mới, đỉnh 'v') vào hàng đợi ưu tiên
                parent[v] = u;  // Cập nhật đỉnh cha 'u' của 'v'
            }
        }
    }

    // In ra các cạnh của cây khung nhỏ nhất (MST)
    for (int i = 1; i < V; i++)  // Duyệt qua các đỉnh từ 1 đến V-1
        cout << parent[i] << " - " << i << " (" << key[i] << ")\n";  // In cạnh (parent[i] - i) và trọng số (key[i])
}