Thuật toán Kruskal

Chi Tiết Kỹ Thuật:

• Khởi tạo một danh sách các cạnh (edges) từ đồ thị ban đầu.
• Sắp xếp danh sách các cạnh theo thứ tự tăng dần của trọng số.
• Khởi tạo một tập hợp con (disjoint set) cho mỗi đỉnh ban đầu trong đồ thị.
• Lặp lại việc chọn cạnh theo thứ tự từ danh sách cạnh đã sắp xếp: a. Lấy ra cạnh có trọng số nhỏ nhất từ danh sách cạnh. b. Kiểm tra xem hai đỉnh của cạnh này có thuộc về cùng một tập hợp con hay không. Nếu không, thêm cạnh này vào cây khung nhỏ nhất và hợp nhất hai tập hợp con lại.
• Lặp lại bước 4 cho đến khi cây khung nhỏ nhất có đủ (V-1) cạnh, trong đó V là số lượng đỉnh của đồ thị ban đầu.

Pseudocode cho Kruskal:

Kruskal(Graph G):
    edges = sorted_edges(G)  # Sắp xếp các cạnh của đồ thị theo trọng số tăng dần
    forest = DisjointSet()   # Khởi tạo một tập hợp con rời rạc (disjoint set)
    MST = []                  # Khởi tạo một danh sách rỗng để lưu trữ cây khung nhỏ nhất

    for each vertex v in G:
        forest.make_set(v)    # Tạo một tập hợp con cho mỗi đỉnh

    for each edge (u, v, w) in edges:
        if forest.find_set(u) ≠ forest.find_set(v):  # Kiểm tra xem hai đỉnh của cạnh này có thuộc về cùng một tập hợp con hay không
            MST.append((u, v, w))                   # Thêm cạnh vào cây khung nhỏ nhất
            forest.union(u, v)                      # Hợp nhất hai tập hợp con lại

    return MST  # Trả về cây khung nhỏ nhất

code C++:

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

using namespace std;

const int V = 6;  // Số lượng đỉnh trong đồ thị

struct Edge {
    int src, dest, weight;  // Cấu trúc lưu trữ thông tin của cạnh (đỉnh nguồn, đỉnh đích, trọng số)
};

// Hàm tìm đại diện (root) của tập hợp chứa phần tử i
int findSet(int i, vector<int>& parent) {
    if (parent[i] == i)
        return i;
    return findSet(parent[i], parent);
}

// Hàm hợp nhất hai tập hợp chứa u và v
void unionSets(int u, int v, vector<int>& parent, vector<int>& rank) {
    int rootU = findSet(u, parent);
    int rootV = findSet(v, parent);
    
    // Nếu hai đỉnh thuộc hai tập hợp khác nhau, hợp nhất chúng lại
    if (rootU != rootV) {
        if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

// Hàm tìm cây khung tối thiểu sử dụng thuật toán Kruskal
vector<Edge> kruskalMST(vector<Edge>& edges) {
    vector<int> parent(V);  // Mảng đại diện cho cha của mỗi đỉnh
    vector<int> rank(V, 0);  // Mảng lưu độ sâu của cây
    vector<Edge> mst;  // Danh sách các cạnh trong cây khung tối thiểu

    // Khởi tạo cấu trúc Union-Find
    for (int i = 0; i < V; ++i)
        parent[i] = i;

    // Sắp xếp các cạnh theo thứ tự tăng dần của trọng số
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    // Duyệt qua các cạnh và thêm vào cây khung tối thiểu nếu không tạo thành chu trình
    for (Edge& edge : edges) {
        if (findSet(edge.src, parent) != findSet(edge.dest, parent)) {
            mst.push_back(edge);
            unionSets(edge.src, edge.dest, parent, rank);
        }
    }

    return mst;
}

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}
    };

    vector<Edge> edges;

    // Chuyển đổi ma trận trọng số thành danh sách các cạnh
    for (int i = 0; i < V; ++i) {
        for (int j = i + 1; j < V; ++j) {
            if (graph[i][j] != 0) {
                edges.push_back({i, j, graph[i][j]});
            }
        }
    }

    // Tìm cây khung tối thiểu sử dụng Kruskal
    vector<Edge> mst = kruskalMST(edges);
    int totalWeight = 0;

    // In ra các cạnh của cây khung tối thiểu và tổng trọng số
    for (Edge& edge : mst) {
        cout << "Canh: " << edge.src << " - " << edge.dest << " voi trong so " << edge.weight << endl;
        totalWeight += edge.weight;
    }

    cout << "Tong trong so cua cay khung toi thieu: " << totalWeight << endl;

    return 0;
}