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

გამოქვეყნებულია: 16 თებერვალი, 2025, 12:32:59 UTC

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

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

Disjoint Set (Union-Find Algorithm) in PHP

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

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

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

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

ყოველ შემთხვევაში, ეს არის 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 მესამე ჯგუფში.

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

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