Thuật toán Kruskal trong lập trình

Thuật toán Kruskal là một thuật toán trong lý thuyết đồ thị để tìm cây bao trùm nhỏ nhất của một đồ thị liên thông có trọng số. Nói cách khác, nó tìm một tập hợp các cạnh tạo thành một cây chứa tất cả các đỉnh của đồ thị và có tổng trọng số các cạnh là nhỏ nhất.Thuật toán Kruskal là một ví dụ của thuật toán tham lam.

Thuật toán này xuất bản lần đầu tiên năm 1956, bởi Joseph Kruskal[1].
Một vài thuật toán khác cho bài toán này bao gồm thuật toán Prim, thuật toán xóa ngược, và thuật toán Borůvka.

Tư tưởng thuật toán

Thuật toán Kruskal dựa trên mô hình xây dựng cây khung nhỏ nhất bằng thuật toán hợp nhất.
Thuật toán không xét các cạnh với thứ tự tuỳ ý.
Thuật toán xét các cạnh theo thứ tự đã sắp xếp theo trọng số.
Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất - tạm gọi là tập K, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau:
Ưu tiên các cạnh có trọng số nhỏ hơn.
Kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó.
Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n - 1 cạnh sẽ là cây khung nhỏ nhất.

Mô tả thuật toán

Giả sử ta cần tìm cây bao trùm nhỏ nhất của đồ thị G. Thuật toán bao gồm các bước sau.
Khởi tạo rừng F (tập hợp các cây), trong đó mỗi đỉnh của G tạo thành một cây riêng biệt
Khởi tạo tập S chứa tất cả các cạnh của G
Chừng nào S còn khác rỗng và F gồm hơn một cây
Xóa cạnh nhỏ nhất trong S
Nếu cạnh đó nối hai cây khác nhau trong F, thì thêm nó vào F và hợp hai cây kề với nó làm một
Nếu không thì loại bỏ cạnh đó.
Khi thuật toán kết thúc, rừng chỉ gồm đúng một cây và đó là một cây bao trùm nhỏ nhất của đồ thị G.
Sau đây là chương trình sử dụng ngôn ngữ lập trình C.

#include <iostream>
#include <climits>
#define n 6
int parent[n]; // Parent array to hold the parent nodes of each node in the graph

using namespace std;

void printMST(int a[n], int b[n], int weight[n]) // Printing the MST
{
    int Minweight = 0; // Weight of Minimum spanning tree
    for (int i = 0; i < n - 1; i++)
    {
        cout << "Edge: " << a[i] << "-" << b[i] << " "
             << "cost: " << weight[i] << endl;
        Minweight += weight[i];
    }
    cout << "Minimum Weight is " << Minweight << endl; // Printing the weight of MINIMUM SPANNING TREE
}

int findParent(int node) // Function to determine the parent node
{
    while(parent[node] >= 0)
        node = parent[node];

    return node;
}

/* "findParentPathCompression" is an alternative for "findParent" which is more efficient.
 * We use a technique called "path compression" here.
 * With path compression, we destroy the structure of the tree, and only focus on which group a node is in.
 */

int findParentPathCompression(int node)
{
    if(node == parent[node]) return node;
    return parent[node] = findParentPathCompression(parent[node]);
}


void kruskal(int cost[n][n]) // Function performing Kruskal's algorithm
{
    fill_n(parent, n, -1);
    int u, v, k = 0, count = 0;
    int firstNode, secondNode;
    int a[n]; // Array containing the first nodes of all the edges present in MST
    int b[n]; // Array containing the second nodes of all the edges present in MST
    int weight[n]; // Array containing the weights of the edges present in MST
    int minimum;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (cost[i][j] == 0) //  If i and j nodes are not adjacent
                cost[i][j] = INT_MAX; // Then, initialize their weight as INFINITE

    while(count < n-1)
    {
        minimum = INT_MAX; // Initializing minimum as INFINITE

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (cost[i][j] < minimum)
                {
                    minimum = cost[i][j]; // find the minimum cost edge
                    firstNode = i; // First node of determined edge
                    secondNode = j; // Second node of determined edge
                }
            }
        }

        u = findParent(firstNode);
        v = findParent(secondNode);


        if (u != v) // If parents of both the nodes are different, no circuit is being formed
        {
            parent[v] = u;
            a[k] = firstNode; // Store first node in array
            b[k] = secondNode; // Store second node in array
            weight[k] = cost[firstNode][secondNode]; // Store the determined edge's weight in array
            count++;
            k++;
        }

        cost[firstNode][secondNode] = cost[secondNode][firstNode] = INT_MAX; // Edges getting included in MST will be given the weight of INFINITE
    }

    printMST(a, b, weight); // Printing the MST
}

// Driver program to test above function
int main()
{

/* Let the given graph is :
     (1)____1___(2)
    /  \       /  \
   3    4     4    6
  /      \   /      \
 /        \ /        \
(0)___5___(5)____5___(3)
 \         |         /
  \        |        /
   \       |       /
    \      2      /
     6     |     8
      \    |    /
       \   |   /
        \  |  /
         \ | /
          (4)
*/

    int cost[n][n] = {
        { 0, 3, 0, 0, 6, 5 },
        { 3, 0, 1, 0, 0, 4 },
        { 0, 1, 0, 6, 0, 4 },
        { 0, 0, 6, 0, 8, 5 },
        { 6, 0, 0, 8, 0, 2 },
        { 5, 4, 4, 5, 2, 0 }
    };

    kruskal(cost);
    return 0;
}

/*
Output :
 Edge: 0-1 cost: 3
 Edge: 1-2 cost: 1
 Edge: 1-5 cost: 4
 Edge: 5-4 cost: 2
 Edge: 5-3 cost: 5
 Minimum Weight is 15
*/