Thuật toán Kruskal

Thuật toán Kruskal và Prim - Tìm Cây Khung Nhỏ Nhất (Minimum Spanning Tree)

Thuật toán Kruskal và Prim - Tìm Cây Khung Nhỏ Nhất (Minimum Spanning Tree)

1. Giới thiệu

Trong lý thuyết đồ thị, bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) là một trong những bài toán cơ bản và quan trọng nhất. Bài toán này có nhiều ứng dụng thực tế trong các lĩnh vực như thiết kế mạng, quy hoạch giao thông, và tối ưu hóa chi phí.

MST

Bài toán: Cho một đồ thị vô hướng có trọng số G với n đỉnh và m cạnh. Ta cần tìm một cây con của đồ thị này sao cho:

  • Cây này kết nối tất cả các đỉnh (spanning tree)
  • Tổng trọng số các cạnh là nhỏ nhất (minimum)

Ví dụ thực tế: Giả sử có n thành phố và với mỗi cặp thành phố, ta biết chi phí để xây dựng một con đường nối chúng (hoặc biết rằng không thể xây dựng được). Ta cần xây dựng các con đường sao cho có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác, và tổng chi phí xây dựng là nhỏ nhất.

Hai thuật toán nổi tiếng nhất để giải quyết bài toán này là thuật toán Kruskal và thuật toán Prim. Cả hai thuật toán đều đảm bảo tìm được cây khung nhỏ nhất, nhưng có cách tiếp cận và hiệu suất khác nhau tùy thuộc vào đặc điểm của đồ thị.

TL;DR: MST là bài toán tìm cách kết nối tất cả đỉnh của đồ thị với tổng trọng số cạnh nhỏ nhất. Hai thuật toán chính: Kruskal và Prim, cả hai đều cho kết quả đúng nhưng hiệu quả khác nhau tùy loại đồ thị.

2. Khái niệm cơ bản

2.1. Spanning Tree (Cây khung)

Một cây khung của đồ thị G là một tập con các cạnh sao cho:

  • Nó kết nối tất cả các đỉnh của đồ thị
  • Không tạo thành chu trình (cycle)
  • Có chính xác n-1 cạnh (với n là số đỉnh)

Nói cách khác, từ bất kỳ đỉnh nào cũng có thể đến được bất kỳ đỉnh nào khác thông qua đúng một đường đi đơn.

TL;DR: Cây khung = Kết nối tất cả đỉnh + Không có chu trình + Đúng n-1 cạnh.

2.2. Minimum Spanning Tree (Cây khung nhỏ nhất)

Cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh là nhỏ nhất trong tất cả các cây khung có thể của đồ thị.

TL;DR: MST = Cây khung với tổng trọng số cạnh nhỏ nhất.

2.3. Các tính chất quan trọng của MST

  1. Tính duy nhất: Nếu trọng số của tất cả các cạnh là khác nhau, thì MST là duy nhất. Nếu không, có thể tồn tại nhiều MST khác nhau.
  2. Tính chất tích: MST cũng là cây có tích trọng số các cạnh là nhỏ nhất. (Điều này có thể chứng minh dễ dàng bằng cách thay thế trọng số của tất cả các cạnh bằng logarit của chúng)
  3. Tính chất cạnh lớn nhất: Trong MST của một đồ thị, trọng số cạnh lớn nhất là nhỏ nhất có thể so với tất cả các cây khung khác.
  4. Maximum Spanning Tree: Có thể tìm cây khung lớn nhất (tổng trọng số các cạnh lớn nhất) bằng cách đổi dấu tất cả các trọng số và áp dụng thuật toán tìm MST.
  5. Số cạnh: Một cây khung của đồ thị n đỉnh luôn có đúng n-1 cạnh.
TL;DR: MST có 5 tính chất quan trọng: (1) Duy nhất nếu trọng số khác nhau, (2) Tích trọng số nhỏ nhất, (3) Cạnh max nhỏ nhất, (4) Đảo dấu để tìm Max ST, (5) Luôn có n-1 cạnh.

3. Thuật toán Kruskal

3.1. Lịch sử

Thuật toán Kruskal được nhà toán học người Mỹ Joseph Bernard Kruskal, Jr. mô tả lần đầu tiên vào năm 1956. Đây là một trong những thuật toán greedy (tham lam) cổ điển và hiệu quả để tìm cây khung nhỏ nhất.

TL;DR: Kruskal (1956) - Thuật toán tham lam cổ điển để tìm MST.

3.2. Ý tưởng chính

Kruskal
Kruskal Animation

Thuật toán Kruskal hoạt động theo nguyên tắc:

  • Ban đầu, xem mỗi đỉnh như một cây riêng biệt (tạo thành một rừng gồm n cây đơn)
  • Dần dần hợp nhất các cây này lại với nhau bằng cách thêm các cạnh
  • Luôn chọn cạnh có trọng số nhỏ nhất chưa được xét và không tạo thành chu trình
  • Tiếp tục cho đến khi tất cả các đỉnh thuộc cùng một cây
TL;DR: Kruskal = Sắp xếp cạnh → Chọn cạnh nhỏ nhất → Hợp nhất cây → Lặp lại đến khi có 1 cây duy nhất.

3.3. Các bước thuật toán

Kruskal Steps

Bước 1: Sắp xếp tất cả các cạnh theo thứ tự tăng dần của trọng số.

Bước 2: Khởi tạo mỗi đỉnh như một cây riêng biệt (sử dụng mảng tree_id[] để đánh dấu mỗi đỉnh thuộc cây nào).

Bước 3: Duyệt qua từng cạnh trong danh sách đã sắp xếp:

  • Nếu hai đầu mút của cạnh thuộc hai cây khác nhau:
  • Thêm cạnh này vào kết quả
  • Hợp nhất hai cây thành một
  • Nếu hai đầu mút cùng thuộc một cây, bỏ qua cạnh này (để tránh chu trình)

Bước 4: Dừng lại khi đã chọn được n-1 cạnh hoặc đã duyệt hết tất cả các cạnh.

TL;DR: 4 bước: (1) Sắp xếp cạnh, (2) Mỗi đỉnh = 1 cây, (3) Chọn cạnh nối 2 cây khác nhau, (4) Dừng khi có n-1 cạnh.

3.4. Cài đặt đơn giản (Java)

Đây là cài đặt trực tiếp theo mô tả thuật toán với độ phức tạp O(M log M + N²):

import java.util.*;

class Edge implements Comparable<Edge> {
    int u, v, weight;

    public Edge(int u, int v, int weight) {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class KruskalSimple {
    int n; // số đỉnh
    List<Edge> edges; // danh sách các cạnh

    public int kruskal() {
        int cost = 0;
        int[] treeId = new int[n];
        List<Edge> result = new ArrayList<>();

        // Khởi tạo mỗi đỉnh thuộc một cây riêng
        for (int i = 0; i < n; i++) {
            treeId[i] = i;
        }

        // Sắp xếp các cạnh theo trọng số tăng dần
        Collections.sort(edges);

        // Duyệt qua từng cạnh
        for (Edge e : edges) {
            // Kiểm tra hai đầu mút có thuộc cùng một cây không
            if (treeId[e.u] != treeId[e.v]) {
                cost += e.weight;
                result.add(e);

                // Hợp nhất hai cây
                int oldId = treeId[e.u];
                int newId = treeId[e.v];
                for (int i = 0; i < n; i++) {
                    if (treeId[i] == oldId) {
                        treeId[i] = newId;
                    }
                }
            }
        }

        return cost;
    }
}
TL;DR: Cài đặt đơn giản: Sắp xếp cạnh → Duyệt từng cạnh → Kiểm tra 2 đỉnh khác cây → Hợp nhất. Độ phức tạp: O(M log M + N²).

3.5. Chứng minh tính đúng đắn

Tại sao thuật toán Kruskal cho ta kết quả đúng?

Chứng minh đồ thị kết quả là cây khung:

  • Nếu đồ thị ban đầu liên thông, đồ thị kết quả cũng sẽ liên thông (vì nếu không, sẽ tồn tại ít nhất một cạnh nối hai thành phần và thuật toán sẽ chọn nó)
  • Đồ thị kết quả không chứa chu trình vì ta chỉ thêm cạnh khi hai đầu mút thuộc hai cây khác nhau
  • Do đó, thuật toán tạo ra một cây khung

Chứng minh cây khung là nhỏ nhất:

Ta sẽ chứng minh mệnh đề: "Nếu F là tập cạnh được chọn bởi thuật toán tại bất kỳ giai đoạn nào, thì tồn tại một MST chứa tất cả các cạnh của F".

  • Khởi đầu: Mệnh đề đúng ở bước đầu vì tập rỗng là tập con của bất kỳ MST nào.
  • Quy nạp: Giả sử F là tập cạnh tại một giai đoạn nào đó, T là MST chứa F, và e là cạnh mới ta muốn thêm.
  • Nếu e tạo chu trình, ta không thêm nó, mệnh đề vẫn đúng.
  • Nếu T đã chứa e, mệnh đề vẫn đúng.
  • Nếu T không chứa e, thì T + e sẽ tạo ra chu trình C. Chu trình này chứa ít nhất một cạnh f không thuộc F. Tập T - f + e cũng là cây khung.
    • Trọng số của f không thể nhỏ hơn e (vì Kruskal đã chọn e trước)
    • Trọng số của f không thể lớn hơn e (vì điều đó làm T - f + e có tổng trọng số nhỏ hơn T, mâu thuẫn với việc T là MST)
    • Vậy trọng số của e bằng trọng số của f
    • Do đó T - f + e cũng là MST và chứa tất cả cạnh từ F + e

Mệnh đề được chứng minh, suy ra sau khi duyệt hết tất cả các cạnh, tập cạnh kết quả sẽ liên thông và được chứa trong một MST, nghĩa là nó chính là MST.

TL;DR: Kruskal đúng vì: (1) Tạo ra cây khung (liên thông + không chu trình), (2) Luôn chọn cạnh nhỏ nhất → Kết quả cuối cùng là MST (chứng minh bằng quy nạp).

3.6. Cải tiến với Disjoint Set Union (DSU)

Để tối ưu hóa phần hợp nhất các cây, ta có thể sử dụng cấu trúc dữ liệu Disjoint Set Union (DSU) hay còn gọi là Union-Find. Điều này giúp giảm độ phức tạp xuống O(M log N).

TL;DR: DSU/Union-Find tối ưu hóa việc hợp nhất cây, giảm độ phức tạp từ O(N²) xuống O(M log N).
class DisjointSetUnion {
    int[] parent, rank;

    public DisjointSetUnion(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return false; // Đã cùng tập hợp
        }

        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

public class KruskalOptimized {
    int n;
    List<Edge> edges;

    public int kruskal() {
        int cost = 0;
        List<Edge> result = new ArrayList<>();
        DisjointSetUnion dsu = new DisjointSetUnion(n);

        Collections.sort(edges);

        for (Edge e : edges) {
            if (dsu.union(e.u, e.v)) {
                cost += e.weight;
                result.add(e);
            }
        }

        return cost;
    }
}

3.7. Độ phức tạp

  • Cài đặt đơn giản: O(M log M + N²)
  • Sắp xếp cạnh: O(M log M) = O(M log N) (vì M ≤ N²)
  • Duyệt qua từng cạnh và hợp nhất cây: O(N) cho mỗi lần hợp nhất, có N-1 lần hợp nhất → O(N²)
  • Cài đặt với DSU: O(M log N)
  • Sắp xếp cạnh: O(M log N)
  • Duyệt qua từng cạnh với DSU: O(M × α(N)) ≈ O(M), với α là hàm Ackermann nghịch đảo (rất nhỏ, coi như hằng số)
TL;DR: Độ phức tạp: Cài đặt đơn giản O(M log M + N²), với DSU chỉ O(M log N).

3.8. Ưu và nhược điểm

Ưu điểm:

  • Đơn giản, dễ hiểu và dễ cài đặt
  • Hoạt động tốt với đồ thị thưa (ít cạnh)
  • Dễ dàng xử lý các cạnh riêng lẻ
  • Có thể dễ dàng tìm các cạnh không thuộc MST

Nhược điểm:

  • Cần sắp xếp tất cả các cạnh trước
  • Không hiệu quả với đồ thị dày đặc (nhiều cạnh)
  • Cần lưu trữ tất cả các cạnh trong bộ nhớ
TL;DR: Kruskal tốt cho đồ thị thưa, đơn giản để cài đặt, nhưng cần sắp xếp cạnh và không tốt với đồ thị dày.

4. Thuật toán Prim

4.1. Lịch sử

Thuật toán Prim có lịch sử khá thú vị:

  • Được phát hiện lần đầu bởi nhà toán học người Séc Vojtěch Jarník vào năm 1930
  • Được nhà toán học người Mỹ Robert Clay Prim phát hiện lại và công bố năm 1957
  • Nhà khoa học máy tính nổi tiếng Edsger Dijkstra cũng công bố thuật toán này vào năm 1959

Do đó, thuật toán này đôi khi còn được gọi là thuật toán Jarník hoặc Prim-Jarník.

TL;DR: Prim được phát hiện 3 lần: Jarník (1930), Prim (1957), Dijkstra (1959).

4.2. Ý tưởng chính

Prim

Thuật toán Prim hoạt động theo nguyên tắc:

  • Bắt đầu từ một đỉnh bất kỳ
  • Dần dần mở rộng cây bằng cách luôn chọn cạnh có trọng số nhỏ nhất nối một đỉnh đã chọn với một đỉnh chưa chọn
  • Tiếp tục cho đến khi tất cả các đỉnh đều được chọn

Khác với Kruskal (làm việc với cạnh và hợp nhất các cây), Prim luôn duy trì một cây duy nhất và mở rộng nó từng bước.

TL;DR: Prim = Bắt đầu từ 1 đỉnh → Mở rộng cây bằng cạnh nhỏ nhất → Lặp lại đến khi chọn hết đỉnh.

4.3. Các bước thuật toán

Prim Algo

Bước 1: Chọn một đỉnh bất kỳ làm đỉnh khởi đầu (thường chọn đỉnh 0).

Bước 2: Đánh dấu đỉnh này là đã chọn.

Bước 3: Lặp lại cho đến khi tất cả các đỉnh đã được chọn:

  • Trong tất cả các cạnh nối một đỉnh đã chọn với một đỉnh chưa chọn, chọn cạnh có trọng số nhỏ nhất
  • Thêm cạnh này vào cây khung
  • Đánh dấu đỉnh mới là đã chọn

Bước 4: Kết thúc khi đã chọn n-1 cạnh (hoặc n đỉnh).

TL;DR: 4 bước: (1) Chọn đỉnh khởi đầu, (2) Đánh dấu đã chọn, (3) Chọn cạnh nhỏ nhất từ đỉnh đã chọn đến chưa chọn, (4) Lặp lại đến khi có n-1 cạnh.

4.4. Chứng minh tính đúng đắn

Giả sử đồ thị G liên thông. Gọi T là đồ thị kết quả của thuật toán Prim, và S là MST.

Chứng minh:

Xét lần đầu tiên trong thuật toán khi ta thêm một cạnh e vào T mà e không thuộc S. Gọi hai đầu mút của e là a và b, với a thuộc tập đỉnh đã chọn V (a ∈ V) và b chưa được chọn (b ∉ V).

Trong MST S, đỉnh a và b được nối với nhau bởi một đường đi P. Trên đường đi này, ta có thể tìm thấy một cạnh f sao cho một đầu của f thuộc V và đầu kia không thuộc V.

Do thuật toán chọn e thay vì f, ta có: trọng số(e) ≤ trọng số(f).

Bây giờ, ta thêm cạnh e vào S và loại bỏ cạnh f:

  • Khi thêm e vào S, ta tạo ra một chu trình
  • Vì f cũng nằm trên chu trình này, nên khi loại f, đồ thị vẫn liên thông và không có chu trình
  • Cây khung kết quả không thể có tổng trọng số lớn hơn vì trọng số(e) ≤ trọng số(f)
  • Nó cũng không thể có tổng trọng số nhỏ hơn vì S là MST
  • Do đó, e phải có cùng trọng số với f

Vậy bằng cách thay f bằng e, ta được một MST khác, và e có cùng trọng số với các cạnh tương ứng trong mọi MST.

Kết luận: Tất cả các cạnh ta chọn trong thuật toán Prim có cùng trọng số với các cạnh trong bất kỳ MST nào, do đó thuật toán Prim thực sự tạo ra MST.

TL;DR: Prim đúng vì luôn chọn cạnh nhỏ nhất từ tập đã chọn sang chưa chọn → Mọi cạnh chọn đều thuộc một MST nào đó.

4.5. Cài đặt cho đồ thị dày đặc - O(n²)

Với đồ thị dày đặc (số cạnh lớn, gần n²), ta sử dụng cài đặt với độ phức tạp O(n²):

import java.util.*;

public class PrimDense {
    int n;
    int[][] adj; // Ma trận kề, adj[i][j] = trọng số cạnh (i,j)
    static final int INF = 1000000000;

    static class Edge {
        int weight = INF;
        int to = -1;
    }

    public int prim() {
        int totalWeight = 0;
        boolean[] selected = new boolean[n];
        Edge[] minEdge = new Edge[n];

        // Khởi tạo
        for (int i = 0; i < n; i++) {
            minEdge[i] = new Edge();
        }
        minEdge[0].weight = 0; // Bắt đầu từ đỉnh 0

        for (int i = 0; i < n; i++) {
            // Tìm đỉnh chưa chọn có cạnh nhỏ nhất
            int v = -1;
            for (int j = 0; j < n; j++) {
                if (!selected[j] && (v == -1 || minEdge[j].weight < minEdge[v].weight)) {
                    v = j;
                }
            }

            // Kiểm tra đồ thị có liên thông không
            if (minEdge[v].weight == INF) {
                System.out.println("No MST!");
                return -1;
            }

            // Chọn đỉnh v
            selected[v] = true;
            totalWeight += minEdge[v].weight;

            // In cạnh được chọn (nếu không phải đỉnh đầu tiên)
            if (minEdge[v].to != -1) {
                System.out.println("Edge: " + v + " - " + minEdge[v].to);
            }

            // Cập nhật các cạnh nhỏ nhất đến các đỉnh chưa chọn
            for (int to = 0; to < n; to++) {
                if (adj[v][to] < minEdge[to].weight) {
                    minEdge[to].weight = adj[v][to];
                    minEdge[to].to = v;
                }
            }
        }

        return totalWeight;
    }
}

Giải thích:

  • Mảng selected[]: Đánh dấu đỉnh đã được chọn
  • Mảng minEdge[]: Lưu cạnh có trọng số nhỏ nhất từ mỗi đỉnh chưa chọn đến các đỉnh đã chọn
  • Mỗi bước: Tìm đỉnh chưa chọn có minEdge nhỏ nhất (O(n)), sau đó cập nhật minEdge cho các đỉnh khác (O(n))
  • Tổng: O(n²)
TL;DR: Cài đặt cho đồ thị dày: Duyệt tuyến tính để tìm đỉnh có cạnh nhỏ nhất. Độ phức tạp O(n²).

4.6. Cài đặt cho đồ thị thưa - O(m log n)

Với đồ thị thưa (số cạnh nhỏ), ta sử dụng cài đặt với Priority Queue (Heap):

import java.util.*;

public class PrimSparse {
    int n;
    List<List<Edge>> adj; // Danh sách kề
    static final int INF = 1000000000;

    static class Edge implements Comparable<Edge> {
        int weight;
        int to;

        public Edge(int weight, int to) {
            this.weight = weight;
            this.to = to;
        }

        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    public int prim() {
        int totalWeight = 0;
        boolean[] selected = new boolean[n];
        int[] minWeight = new int[n];
        int[] parent = new int[n];

        Arrays.fill(minWeight, INF);
        Arrays.fill(parent, -1);

        // Priority Queue để lấy đỉnh có cạnh nhỏ nhất
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        // Bắt đầu từ đỉnh 0
        minWeight[0] = 0;
        pq.offer(new Edge(0, 0));

        for (int i = 0; i < n; i++) {
            // Lấy đỉnh có cạnh nhỏ nhất
            if (pq.isEmpty()) {
                System.out.println("No MST!");
                return -1;
            }

            int v = -1;
            while (!pq.isEmpty()) {
                v = pq.poll().to;
                if (!selected[v]) break;
            }

            if (v == -1 || selected[v]) {
                System.out.println("No MST!");
                return -1;
            }

            // Chọn đỉnh v
            selected[v] = true;
            totalWeight += minWeight[v];

            // In cạnh được chọn
            if (parent[v] != -1) {
                System.out.println("Edge: " + v + " - " + parent[v]);
            }

            // Cập nhật các đỉnh kề
            for (Edge edge : adj.get(v)) {
                int to = edge.to;
                int weight = edge.weight;

                if (!selected[to] && weight < minWeight[to]) {
                    minWeight[to] = weight;
                    parent[to] = v;
                    pq.offer(new Edge(weight, to));
                }
            }
        }

        return totalWeight;
    }
}

Giải thích:

  • Sử dụng PriorityQueue để luôn lấy được đỉnh có cạnh nhỏ nhất trong O(log n)
  • Mỗi cạnh được thêm vào queue tối đa một lần
  • Tổng: O(m log n) với m là số cạnh
TL;DR: Cài đặt cho đồ thị thưa: Dùng Priority Queue để tìm nhanh đỉnh có cạnh nhỏ nhất. Độ phức tạp O(m log n).

4.7. Độ phức tạp

  • Cài đặt đơn giản (duyệt tuyến tính): O(n²)
  • Mỗi bước tìm đỉnh có cạnh nhỏ nhất: O(n)
  • Cập nhật các cạnh: O(n)
  • Tổng n bước: O(n²)
  • Cài đặt với Priority Queue: O(m log n)
  • Mỗi cạnh được thêm/xóa khỏi queue: O(log n)
  • Tổng có m cạnh: O(m log n)
  • Cải tiến với Fibonacci Heap: O(m + n log n)
  • Hiếm khi được sử dụng trong thực tế do overhead lớn
TL;DR: Độ phức tạp Prim: O(n²) với mảng, O(m log n) với Heap, O(m + n log n) với Fibonacci Heap.

4.8. Ưu và nhược điểm

Ưu điểm:

  • Hiệu quả với đồ thị dày đặc khi dùng cài đặt O(n²)
  • Không cần lưu trữ tất cả các cạnh
  • Dễ dàng theo dõi quá trình xây dựng cây từ một đỉnh cụ thể
  • Thích hợp cho bài toán Euclidean MST (n điểm trên mặt phẳng)

Nhược điểm:

  • Phức tạp hơn Kruskal trong cài đặt
  • Phụ thuộc vào việc chọn đỉnh bắt đầu (mặc dù kết quả vẫn đúng)
  • Cần cấu trúc dữ liệu phức tạp hơn cho đồ thị thưa
TL;DR: Prim tốt cho đồ thị dày, không cần lưu tất cả cạnh, nhưng phức tạp hơn Kruskal để cài đặt.

5. So sánh Kruskal và Prim

5.1. Điểm giống nhau

  1. Cùng giải quyết bài toán MST: Cả hai thuật toán đều đảm bảo tìm được cây khung nhỏ nhất.
  2. Đều là thuật toán tham lam (Greedy): Cả hai đều luôn chọn cạnh tốt nhất tại mỗi bước mà không cần xem xét lại.
  3. Độ phức tạp tương đương (trong trường hợp tối ưu):
  • Kruskal với DSU: O(m log n)
  • Prim với Priority Queue: O(m log n)
  1. Tính đúng đắn: Cả hai đều có chứng minh toán học chặt chẽ.
  2. Kết quả giống nhau: Nếu đồ thị có các cạnh có trọng số khác nhau, cả hai sẽ cho cùng một MST.
TL;DR: Cả hai đều là thuật toán tham lam, cho kết quả MST đúng, độ phức tạp tối ưu O(m log n).

5.2. Điểm khác nhau

Tiêu chíKruskalPrim
Cách tiếp cậnLàm việc với cạnh, hợp nhất các cây conLàm việc với đỉnh, mở rộng một cây duy nhất
Điểm khởi đầuKhông cần chọn đỉnh khởi đầuCần chọn một đỉnh để bắt đầu
Cấu trúc dữ liệu chínhDanh sách cạnh + DSUMa trận kề hoặc danh sách kề + Heap
Cần sắp xếp?Phải sắp xếp tất cả các cạnh trướcKhông cần sắp xếp trước
Hiệu quả với đồ thị dày đặcKém hiệu quả (nhiều cạnh cần sắp xếp)Rất hiệu quả với cài đặt O(n²)
Hiệu quả với đồ thị thưaRất hiệu quảHiệu quả với Priority Queue
Độ phức tạp tốt nhấtO(m log n) với DSUO(n²) cho dày đặc, O(m log n) cho thưa
Dễ cài đặtĐơn giản hơnPhức tạp hơn một chút
Sử dụng bộ nhớCần lưu tất cả các cạnhCó thể làm việc với ma trận kề

TL;DR: Kruskal làm việc với cạnh (sắp xếp + hợp nhất), Prim làm việc với đỉnh (mở rộng từ 1 cây).

5.3. Khi nào nên dùng thuật toán nào?

Nên dùng Kruskal khi:

  • Đồ thị thưa (số cạnh m gần với n)
  • Danh sách cạnh đã có sẵn
  • Cần tìm các cạnh không thuộc MST
  • Muốn cài đặt đơn giản
  • Đồ thị không được lưu dưới dạng ma trận kề

Nên dùng Prim khi:

  • Đồ thị dày đặc (số cạnh m gần với n²)
  • Đồ thị được lưu dưới dạng ma trận kề
  • Không muốn sắp xếp tất cả các cạnh trước
  • Bài toán Euclidean MST (n điểm trên mặt phẳng)
  • Muốn xây dựng cây từ một đỉnh cụ thể

Ví dụ cụ thể:

  • Đồ thị 1000 đỉnh, 2000 cạnh (thưa): Dùng Kruskal
  • Đồ thị 1000 đỉnh, 500,000 cạnh (dày): Dùng Prim
  • Bài toán kết nối các thành phố với ít đường nối: Kruskal
  • Bài toán mạng lưới điện với nhiều kết nối: Prim
TL;DR: Đồ thị thưa → Kruskal. Đồ thị dày → Prim. Muốn đơn giản → Kruskal.

5.4. Bảng so sánh độ phức tạp

Loại đồ thịKruskal (DSU)Prim (Array)Prim (Heap)Tốt nhất
Thưa (m ≈ n)O(n log n)O(n²)O(n log n)Kruskal/Prim-Heap
Trung bìnhO(m log n)O(n²)O(m log n)Tùy m
Dày (m ≈ n²)O(n² log n)O(n²)O(n² log n)Prim-Array
TL;DR: Đồ thị thưa: Kruskal/Prim-Heap tốt nhất. Đồ thị dày: Prim-Array tốt nhất.

6. Kết luận

Thuật toán Kruskal và Prim là hai thuật toán cổ điển và hiệu quả để giải quyết bài toán tìm cây khung nhỏ nhất. Mỗi thuật toán có ưu điểm riêng và phù hợp với các loại đồ thị khác nhau.

Những điểm quan trọng cần nhớ:

  1. MST là cây khung có tổng trọng số nhỏ nhất, kết nối tất cả các đỉnh với đúng n-1 cạnh.
  2. Kruskal hoạt động bằng cách chọn các cạnh từ nhỏ đến lớn và hợp nhất các cây con, phù hợp với đồ thị thưa.
  3. Prim hoạt động bằng cách mở rộng một cây duy nhất từ một đỉnh, phù hợp với đồ thị dày đặc.
  4. Cả hai đều là thuật toán tham lam và đều đảm bảo tìm được MST.
  5. Lựa chọn thuật toán phụ thuộc vào:
  • Đặc điểm của đồ thị (thưa hay dày)
  • Cách biểu diễn đồ thị
  • Yêu cầu về hiệu suất
  1. Trong thực tế:
  • Đồ thị thưa: Dùng Kruskal với DSU
  • Đồ thị dày: Dùng Prim với ma trận kề
  • Chưa rõ: Hãy thử cả hai và đo thời gian!

Cả hai thuật toán đều là những công cụ mạnh mẽ trong hộp công cụ của lập trình viên, và việc hiểu rõ cách hoạt động cũng như ưu nhược điểm của chúng sẽ giúp bạn giải quyết hiệu quả các bài toán liên quan đến đồ thị.

TL;DR: MST = Cây nối tất cả đỉnh với tổng trọng số nhỏ nhất. Kruskal tốt cho đồ thị thưa (sắp xếp cạnh + hợp nhất). Prim tốt cho đồ thị dày (mở rộng từ 1 đỉnh). Chọn thuật toán tùy vào loại đồ thị.

Tài liệu tham khảo:

  • Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem"
  • Prim, R. C. (1957). "Shortest connection networks and some generalizations"
  • Jarník, V. (1930). "O jistém problému minimálním"
  • Cormen, T. H., et al. "Introduction to Algorithms"

Read more