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

Bài viết này giới thiệu về 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 khung nhỏ nhất.

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

Disjoint Set (thường được sử dụng cho Union-Find hay còn gọi là Disjoint Set Union) 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 hợ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 phần tử thuộc tập hợp nào.
Hợp : Gộp hai tập hợp lại với nhau.

Cấu trúc này đặc biệt hữu ích trong các thuật toán cây khung nhỏ nhất, chẳng hạn như thuật toán Kruskal.

Tôi có một triển khai thuật toán Kruskal được sử dụng để tạo ra các mê cung ngẫu nhiên dựa trên 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 đi nữa, đây là cách triển khai Disjoint Set bằng PHP của tôi:

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 ra 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 gợi ý những người bạn mới cho người dùng và giả sử chúng ta đã có sáu người có mối quan hệ bạn bè như sau:

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 kết quả sau:

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

Dựa trên điều này, sẽ hợp lý khi đề xuất rằng 1 và 3 nên trở thành bạn bè, 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 nhận ra sự thật này, nhưng hiệu quả của thuật toán này cho phép nó có thể mở rộng khả thi tới hàng tỷ người và nhóm bạn bè.