Bài 5: Union-Find / Disjoint Set — Kruskal MST

Ở Bài 4 chúng ta tối ưu tìm kiếm chuỗi bằng Trie. Bài này quay lại đồ thị (như Bài 2) nhưng với một câu hỏi khác hẳn Dijkstra: không phải "đường ngắn nhất từ A tới B", mà là "A và B có đang thuộc cùng một thành phần liên thông hay không?" — và làm sao trả lời cực nhanh khi đồ thị liên tục được thêm cạnh mới.

1. Bài toán: Kiểm tra kết nối động (Dynamic Connectivity)

Giả sử bạn có $n$ node rời rạc, và liên tục nhận các cạnh nối 2 node lại với nhau theo thời gian thực. Sau mỗi cạnh mới, bạn cần trả lời ngay: "X và Y có đang cùng nhóm không?". Cách ngây thơ là chạy BFS/DFS từ X mỗi lần hỏi — tốn $O(V+E)$ mỗi truy vấn. Nếu có hàng triệu truy vấn xen kẽ hàng triệu cạnh mới, cách này quá chậm.

Union-Find (hay Disjoint Set Union — DSU) giải quyết đúng bài toán này: duy trì các node dưới dạng rừng cây, mỗi cây là một "nhóm liên thông". Hai thao tác cốt lõi: find(x) — tìm đại diện (root) của nhóm chứa x, và union(x, y) — gộp 2 nhóm chứa x và y làm một.

2. Cấu trúc cơ bản: Mảng Parent

Cài đặt ngây thơ nhất: mỗi node lưu con trỏ tới "cha" của nó trong mảng parent. Ban đầu mỗi node tự làm cha của chính mình (nhóm riêng). union(x, y) nối root của x làm cha của root của y:

class NaiveUnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i); // mỗi node tự làm root
  }

  find(x) {
    while (this.parent[x] !== x) x = this.parent[x]; // đi ngược lên root
    return x;
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // đã cùng nhóm — sẽ tạo chu trình
    this.parent[rootX] = rootY; // gộp nhóm x vào nhóm y
    return true;
  }
}

3. Tối ưu hoá: Path Compression & Union by Rank

Hai kỹ thuật sau biến Union-Find từ $O(n)$ trường hợp xấu nhất thành gần như hằng số:

Path Compression: mỗi lần gọi find(x), sau khi tìm ra root, gắn thẳng mọi node trên đường đi trực tiếp về root đó — lần tìm sau sẽ chỉ mất 1 bước. Union by Rank: khi union, luôn gắn cây thấp hơn vào dưới cây cao hơn — tránh tạo ra cây lệch sâu ngay từ đầu.

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0); // ước lượng chiều cao cây
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // PATH COMPRESSION: gắn thẳng về root
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // cùng nhóm rồi — sẽ tạo chu trình

    // UNION BY RANK: gắn cây thấp hơn vào dưới cây cao hơn
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    return true;
  }
}

4. Ứng dụng: Thuật toán Kruskal tìm Cây Khung Nhỏ Nhất

Cây khung nhỏ nhất (Minimum Spanning Tree — MST) là tập cạnh ít nhất nối mọi node trong đồ thị lại với nhau, sao cho tổng trọng số nhỏ nhất. Thuật toán Kruskal (Joseph Kruskal, 1956) cực kỳ đơn giản nhờ Union-Find: sắp xếp mọi cạnh theo trọng số tăng dần, rồi lần lượt xét — nếu 2 đầu cạnh chưa cùng nhóm, nhận cạnh và union; nếu đã cùng nhóm, từ chối (vì nhận sẽ tạo chu trình thừa):

function kruskalMST(numNodes, edges) {
  // edges: [{ u, v, weight }, ...]
  const sorted = edges.slice().sort((a, b) => a.weight - b.weight);
  const dsu = new UnionFind(numNodes);
  const mst = [];
  let totalWeight = 0;

  for (const edge of sorted) {
    // union() tự trả về false nếu u,v đã cùng nhóm (sẽ tạo chu trình)
    if (dsu.union(edge.u, edge.v)) {
      mst.push(edge);
      totalWeight += edge.weight;
    }
  }
  return { mst, totalWeight };
}

Điều đẹp nhất: kiểm tra chu trình (cycle detection) — phần khó nhất khi cài Kruskal bằng tay — chỉ gọn trong 1 lệnh if (dsu.union(...)), vì union() đã tự trả về false khi 2 đầu cạnh cùng nhóm.

5. So sánh Union-Find với BFS/DFS cho bài toán liên thông

Sân chơi tương tác: Kruskal MST Visualizer

Bấm "Chạy Kruskal" để xem thuật toán xét từng cạnh theo trọng số tăng dần trên đồ thị 8 node mẫu — cạnh được chấp nhận chuyển xanh lá, cạnh bị từ chối (vì tạo chu trình) chuyển xám mờ, màu node thay đổi theo nhóm liên thông hiện tại.