Tập hợp rời rạc (Thuật toán hợp nhất-tìm kiếm) trong PHP

Đã xuất bản: lúc 12:28:38 UTC 16 tháng 2, 2025
Cập nhật lần cuối: lúc 10:37:03 UTC 26 tháng 1, 2026

Bài viết này trình bày một triển khai PHP của cấu trúc dữ liệu Disjoint Set, thường được sử dụng cho Union-Find trong các thuật toán cây spanning tối thiểu.

Trang này được dịch máy từ tiếng Anh để có thể tiếp cận được với nhiều người nhất có thể. Thật không may, dịch máy vẫn chưa phải là công nghệ hoàn thiện, do đó có thể xảy ra lỗi. Nếu bạn thích, bạn có thể xem phiên bản tiếng Anh gốc tại đây:

Disjoint Set (Union-Find Algorithm) in PHP

Tập rời rạc (thường được sử dụng cho Union-Find hay còn gọi là Liên hợp tập rời rạc) là một cấu trúc dữ liệu được sử dụng để quản lý phân vùng các phần tử thành các tập rời rạc (không chồng chéo). Nó hỗ trợ hai hoạt động chính một cách hiệu quả:

Tìm: Xác định tập hợp một phần tử thuộc về.
Union: Hợp nhất hai bộ với nhau.

Cấu trúc này đặc biệt hữu ích trong các thuật toán cây kéo dài tối thiểu, chẳng hạn như thuật toán của Kruskal.

Tôi có một triển khai thuật toán của Kruskal được sử dụng để tạo ra các mê cung ngẫu nhiên dựa trên việc triển khai PHP bên dưới của Disjoint Set để hợp nhất các tập hợp một cách hiệu quả. Nếu bạn quan tâm, bạn có thể xem nó hoạt động tại đây: Máy phát mê cung thuật toán Kruskal

Dù sao, đây là cách triển khai PHP của tôi cho Disjoint Set:

class DisjointSet 
{
    private $parent = [];
    private $rank   = [];

    public function __construct($size) 
    {
        for ($i = 0; $i < $size; $i++) 
        {
            $this->parent[$i]   = $i;
            $this->rank[$i]     = 0;
        }
    }

    public function find($x) 
    {
        if ($this->parent[$x] != $x) 
        {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }

        return $this->parent[$x];
    }

    public function union($x, $y) 
    {
        $rootX = $this->find($x);
        $rootY = $this->find($y);

        if ($rootX != $rootY) 
        {
            if ($this->rank[$rootX] > $this->rank[$rootY]) 
            {
                $this->parent[$rootY] = $rootX;
            }
            elseif ($this->rank[$rootX] < $this->rank[$rootY]) 
            {
                $this->parent[$rootX] = $rootY;
    
            }
            else
            {
                $this->parent[$rootY] = $rootX;
                $this->rank[$rootX]++;
            }
        }
    }
}

Ngoài việc tạo mê cung để giải trí, cấu trúc dữ liệu Disjoint Set chắc chắn cũng có thể được sử dụng cho các tình huống thực tế.

Ví dụ, hãy tưởng tượng một mạng xã hội muốn đề xuất bạn bè mới cho người dùng của nó, và sau đó giả sử rằng chúng ta có sáu người có các mối quan hệ bạn bè này:

1 và 2 là bạn.
2 và 3 là bạn.
4 và 5 là bạn.
6 không có bạn bè.

Áp dụng thuật toán Union-Find cho các nhóm riêng biệt này, chúng ta sẽ tìm thấy những điều sau:

1, 2 và 3 trong một nhóm.
4 và 5 trong nhóm thứ hai.
6 trong nhóm thứ ba.

Dựa trên điều này, sẽ có ý nghĩa khi đề xuất rằng 1 và 3 nên trở thành bạn bè, bởi vì họ có chung người 2.

Tất nhiên, trong một ví dụ nhỏ như thế này, bạn có thể dễ dàng tự mình phát hiện ra thực tế này, nhưng hiệu quả của thuật toán này cho phép nó mở rộng quy mô khả thi lên hàng tỷ người và nhóm bạn.