Thuật toán Prim

Ý tưởng chính:

1. Khởi tạo: Chọn một đỉnh bất kỳ làm đỉnh xuất phát và đánh dấu nó đã được thăm.
2. Lặp lại cho đến khi tất cả các đỉnh đều đã được thăm:
   • Chọn cạnh nhỏ nhất từ tập hợp các cạnh nối đỉnh đã được thăm và đỉnh chưa được thăm.
   • Đánh dấu đỉnh được thêm vào và cạnh được chọn làm phần của cây khung.

Chi tiết thuật toán:

1. Khởi tạo:

   • Khởi tạo một tập hợp rỗng là cây khung.
   • Khởi tạo một mảng key[] với giá trị vô cùng lớn (hoặc vô cùng nhỏ tùy thuộc vào trọng số của đồ thị), biểu diễn trọng số nhỏ nhất của cạnh nối mỗi đỉnh với cây khung hiện tại.
   • Khởi tạo một mảng parent[] để lưu trữ cây khung được tạo ra, ban đầu tất cả các phần tử đều là -1.

2. Lặp lại cho đến khi tất cả các đỉnh đều đã được thăm:

   • Chọn đỉnh có key[] nhỏ nhất và chưa được thăm. Đây là bước tham lam của thuật toán.
   • Đánh dấu đỉnh đã được thăm và cập nhật key[] và parent[] cho các đỉnh kề chưa được thăm.
   • Lặp lại các bước trên cho đến khi tất cả các đỉnh đều đã được thăm.

Pseudocode Prim:

PrimMST(G): // Thuật toán Prim để tìm cây khung nhỏ nhất trong đồ thị G
    V = G.V // Danh sách các đỉnh trong đồ thị
    E = G.E // Danh sách các cạnh trong đồ thị

    // Khởi tạo
    Q = priority_queue() // Hàng đợi ưu tiên để lưu trữ các cạnh
    inMST = [False] * len(V) // Đánh dấu các đỉnh đã nằm trong cây khung MST
    parent = [-1] * len(V) // Mảng lưu trữ đỉnh cha của mỗi đỉnh trong MST
    key = [inf] * len(V) // Mảng lưu trữ trọng số nhỏ nhất cho mỗi đỉnh

    // Bắt đầu từ đỉnh đầu tiên
    key[0] = 0 // Trọng số của đỉnh bắt đầu là 0
    Q.insert((0, 0)) // Đưa đỉnh bắt đầu vào hàng đợi với trọng số 0

    while not Q.empty(): // Lặp lại cho đến khi hàng đợi rỗng
        weight, u = Q.extract_min() // Lấy đỉnh u có trọng số nhỏ nhất ra khỏi hàng đợi

        inMST[u] = True // Đánh dấu đỉnh u đã nằm trong cây khung MST

        for v, weight in G.adj[u]: // Duyệt qua các đỉnh kề của u
            if not inMST[v] and weight < key[v]: // Nếu đỉnh v chưa nằm trong MST và trọng số nhỏ hơn key[v]
                key[v] = weight // Cập nhật trọng số nhỏ nhất cho đỉnh v
                parent[v] = u // Đặt u làm cha của v trong MST
                Q.insert((weight, v)) // Thêm hoặc cập nhật đỉnh v trong hàng đợi với trọng số mới

    // Trả về danh sách các cạnh trong MST
    result = []
    for i in range(1, len(V)):
        result.append((parent[i], i, key[i])) // Thêm cạnh (parent[i], i) vào danh sách kết quả với trọng số key[i]

    return result // Trả về cây khung nhỏ nhất dưới dạng danh sách các cạnh
 

code C++:

//https://nguyenvanhieu.vn/thuat-toan-prim/
#include <bits/stdc++.h>
using namespace std;

#define V 6 // Số đỉnh của đồ thị
#define INF INT_MAX

typedef pair<int, int> iPair;

// Biến toàn cục để lưu thứ tự các đỉnh được thăm
vector<int> visitedOrder;

void initialize(int key[], bool inMST[], int parent[], int src) {
    fill(key, key + V, INF);
    fill(inMST, inMST + V, false);
    parent[src] = -1;
    key[src] = 0;
}

void printPath(int parent[], int j) {
    if (parent[j] == -1) {
        cout << j;
        return;
    }
    printPath(parent, parent[j]);
    cout << " -> " << j;
}

void printTotalWeight(int parent[], int graph[V][V]) {
    int totalWeight = 0;
    for (int i = 1; i < V; ++i) {
        totalWeight += graph[i][parent[i]];
    }
    cout << "\nTong trong so cua cay khung toi thieu: " << totalWeight << "\n";
}

void updatePriorityQueue(int u, int key[], int parent[], bool inMST[], int graph[V][V], priority_queue<iPair, vector<iPair>, greater<iPair>> &pq) {
    inMST[u] = true;
    visitedOrder.push_back(u); // Thêm đỉnh vào thứ tự được thăm
    for (int v = 0; v < V; ++v) {
        int weight = graph[u][v];
        if (weight && !inMST[v] && weight < key[v]) {
            key[v] = weight;
            pq.push({key[v], v});
            parent[v] = u;
        }
    }
}

void printVisitedOrder() {
    cout << "Thu tu cac dinh duoc tham:\n";
    for (int i = 0; i < visitedOrder.size(); ++i) {
        cout << visitedOrder[i];
        if (i != visitedOrder.size() - 1)
            cout << " -> ";
    }
    cout << "\n";
}

void primMST(int graph[V][V], int src) {
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
    int key[V];
    int parent[V];
    bool inMST[V];

    initialize(key, inMST, parent, src);
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (!inMST[u]) {
            updatePriorityQueue(u, key, parent, inMST, graph, pq);
        }
    }

    printVisitedOrder();

    cout << "Duong di cua cay khung toi thieu tu dinh " << src << ":\n";
    for (int i = 0; i < V; ++i) {
        if (i != src) {
            cout << "Duong di den dinh " << i << ": ";
            printPath(parent, i);
            cout << "\t(Trong so: " << graph[i][parent[i]] << ")\n";
        }
    }

    printTotalWeight(parent, graph);
}

int main() {
    int graph[V][V] = {
        {0, 6, 1, 5, 0, 0},
        {6, 0, 5, 0, 3, 0},
        {1, 5, 0, 5, 6, 4},
        {5, 0, 5, 0, 0, 2},
        {0, 3, 6, 0, 0, 6},
        {0, 0, 4, 2, 6, 0}
    };

    int src = 0; // Đỉnh nguồn
    primMST(graph, src);

    return 0;
}