Disjoint Set (Union-Find Algorithm) PHP-ში

გამოქვეყნებულია: 16 თებერვალი, 2025, 12:32:59 UTC
ბოლო განახლება: 26 იანვარი, 2026, 10:37:14 UTC

ამ სტატიაში მოცემულია Disjoint Set მონაცემთა სტრუქტურის PHP განხორციელება, რომელიც ჩვეულებრივ გამოიყენება Union-Find-ისთვის მინიმალურ ხის ალგორითმებში.

ეს გვერდი მანქანურად ითარგმნა ინგლისურიდან, რათა რაც შეიძლება მეტი ადამიანისთვის ხელმისაწვდომი ყოფილიყო. სამწუხაროდ, მანქანური თარგმანი ჯერ კიდევ არ არის სრულყოფილი ტექნოლოგია, ამიტომ შეიძლება მოხდეს შეცდომები. თუ გსურთ, შეგიძლიათ ნახოთ ორიგინალური ინგლისური ვერსია აქ:

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (ჩვეულებრივ გამოიყენება Union-Find aka Disjoint Set Union-ისთვის) არის მონაცემთა სტრუქტურა, რომელიც გამოიყენება ელემენტების დაყოფის სამართავად დაცალკევებულ (არაგადახურულ) კომპლექტებად. ის ეფექტურად უჭერს მხარს ორ ძირითად ოპერაციას:

ძებნა: განსაზღვრავს, რომელ კომპლექტს ეკუთვნის ელემენტი.
კავშირი: აერთიანებს ორ კომპლექტს ერთად.

ეს სტრუქტურა განსაკუთრებით სასარგებლოა მინიმალური ხის ალგორითმებში, როგორიცაა კრუსკალის ალგორითმი.

მე მაქვს კრუსკალის ალგორითმის განხორციელება, რომელიც გამოიყენება შემთხვევითი ლაბირინთების შესაქმნელად, რომელიც ეყრდნობა Disjoint Set-ის ქვემოთ მოცემულ PHP განხორციელებას კომპლექტების ეფექტურად შერწყმისთვის. თუ გაინტერესებთ, შეგიძლიათ ნახოთ აქ: ბმული კრუსკალის ალგორითმის ლაბირინთში გენერატორი

ყოველ შემთხვევაში, ეს არის ჩემი PHP განხორციელება 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]++;
            }
        }
    }
}

გართობისთვის ლაბირინთების გენერირების გარდა, Disjoint Set მონაცემთა სტრუქტურა, რა თქმა უნდა, ასევე შეიძლება გამოყენებულ იქნას რეალურ სცენარებში.

წარმოიდგინეთ, მაგალითად, სოციალური ქსელი, რომელსაც სურს შესთავაზოს ახალი მეგობრები თავის მომხმარებლებს, შემდეგ კი ვთქვათ, რომ ჩვენ გვყავს ექვსი ადამიანი, რომლებსაც აქვთ ეს მეგობრული ურთიერთობები უკვე ადგილზეა:

1 და 2 მეგობრები არიან.
2 და 3 მეგობრები არიან.
4 და 5 მეგობრები არიან.
6 მეგობარი არ ჰყავს.

კავშირის ძებნის ალგორითმის გამოყენებით ამ ცალკეულ ჯგუფებზე, ჩვენ უნდა ვიპოვოთ შემდეგი:

1, 2 და 3 ერთ ჯგუფში.
მე-4 და მე-5 მეორე ჯგუფში.
6 მესამე ჯგუფში.

აქედან გამომდინარე, აზრი ექნება ვარაუდობდეს, რომ 1 და 3 უნდა გახდნენ მეგობრები, რადგან მათ აქვთ საერთო პირი 2.

რა თქმა უნდა, მსგავს პატარა მაგალითში, თქვენ შეგიძლიათ მარტივად შეამჩნიოთ ეს ფაქტი, მაგრამ ამ ალგორითმის ეფექტურობა საშუალებას აძლევს მას მაქსიმალურად გააფართოვოს მილიარდობით ადამიანზე და მეგობრების ჯგუფებზე.