Untitled

Thuật toán Kruskal là một thuật toán tìm cây khung nhỏ nhất trong đồ thị. Nó hoạt động bằng cách sắp xếp tất cả các cạnh theo trọng số tăng dần và thêm từng cạnh vào cây khung một cách lần lượt. Trước khi thêm một cạnh vào cây khung, thuật toán sẽ kiểm tra xem cạnh đó có tạo thành chu trình với các cạnh đã được thêm vào cây khung hay không. Nếu không tạo thành chu trình, cạnh đó sẽ được thêm vào cây khung.

Đây là một ví dụ về cách triển khai thuật toán Kruskal bằng Java:

```java
import java.util.Arrays;

public class Kruskal {
    public static int kruskal(int[][] graph) {
        int n = graph.length;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int[][] edges = new int[n * (n - 1) / 2][3];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] != 0) {
                    edges[idx++] = new int[]{i, j, graph[i][j]};
                }
            }
        }
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        int res = 0;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            int pu = find(u, parent), pv = find(v, parent);
            if (pu != pv) {
                res += w;
                parent[pu] = pv;
            }
        }
        return res;
    }

    private static int find(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }
}
```

Bạn có thể sử dụng mã này như một cơ sở để giải quyết bài toán của mình. Bạn có muốn biết thêm chi tiết gì không?