PHP хэл дээрх Disjoint Set (Union-Find Algorithm).

Нийтэлсэн: 2025 оны гуравдугаар сарын 19 21:36:30 (UTC)
Хамгийн сүүлд шинэчлэгдсэн: 2026 оны нэгдүгээр сарын 26 10:37:20 (UTC)

Энэ нийтлэлд хамгийн бага хүрээтэй модны алгоритмд Union-Find-д ихэвчлэн ашиглагддаг Disjoint Set өгөгдлийн бүтцийн PHP хэрэгжилтийг харуулсан.

Энэ хуудсыг аль болох олон хүнд хүртээмжтэй болгох үүднээс англи хэлнээс орчуулсан. Харамсалтай нь машин орчуулга нь төгс төгөлдөр технологи болоогүй байгаа тул алдаа гарч болзошгүй. Хэрэв та хүсвэл англи хэл дээрх эх хувилбарыг эндээс үзэх боломжтой.

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (Union-Find буюу Disjoint Set Union гэж нэрлэгддэг) нь элементийг тусдаа (зэрэгцэхгүй) багцад хуваарилах бүтцийг удирдах зориулалттай өгөгдлийн бүтэц юм. Энэ нь хоёр гол үйлдлийг үр дүнтэйгээр дэмждэг:

Find: Элемент ямар багцад хамаарагдаж байгааг тодорхойлно.
Union: Хоёр багцыг нэгдэх.

Энэ бүтэц нь Kruskal-ийн алгоритм зэрэг хамгийн бага тархалтын модны алгоритмуудад тусгайлсан хэрэглээтэй.

Би Kruskal-ийн алгоритмын хэрэгжилттэй бөгөөд энэ нь доорх PHP хэрэгжилт дээр тулгуурлан тасархай багцуудыг үр дүнтэй нэгдэх зориулалттай. Хэрэв сонирхож байвал, үүнийг эндээс ажиглаж болно: Крускалийн алгоритм төөрдөг байшин үүсгэгч

Ямар ч байсан, энэ бол миний Disjoint Set-ийн PHP хэрэгжилт:

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]++;
            }
        }
    }
}

Зөвхөн хөгжилд зориулан лабиринт үүсгэхээс гадна, Disjoint Set өгөгдлийн бүтэц бодит амьдралын нөхцөлд ч ашиглагдах боломжтой.

Жишээ нь, нийгмийн сүлжээ нь хэрэглэгчдэд шинэ найзууд санал болгож байгааг төсөөлөөд үзье. Бидэнд зургаан хүн дараах найзын харилцаатай байгаа гэж үзье:

1 ба 2 найзууд.
2 ба 3 найзууд.
4 ба 5 найзууд.
6 ямар ч найзгүй.

Эдгээр тусдаа бүлгүүд дээр Union-Find алгоритм хэрэглэхэд дараах үр дүнгүүдийг олох ёстой:

1, 2 ба 3 нэг бүлэгт.
4 ба 5 хоёр дахь бүлэгт.
6 гурав дахь бүлэгт.

Мэдээж, ийм жижиг жишээ дээр та өөрөө энэ баримтыг амархан олох боломжтой, гэхдээ энэ алгоритмын үр ашиг нь тэрээр тэрбум хүн, найзуудын бүлгүүдийг бодитойгоор өргөжүүлэх боломжтой болгодог.