PHP-də Disjoint Set (Union-Find Alqoritmi).

Nəşr olundu: 16 fevral 2025 at 12:34:26 UTC

Bu məqalədə minimum əhatəli ağac alqoritmlərində Union-Find üçün istifadə olunan Disjoint Set məlumat strukturunun PHP tətbiqi təqdim olunur.

Bu səhifə mümkün qədər çox insan üçün əlçatan olması üçün ingilis dilindən maşın tərcümə edilib. Təəssüf ki, maşın tərcüməsi hələ mükəmməl texnologiya deyil, ona görə də səhvlər baş verə bilər. İstəyirsinizsə, orijinal ingilis versiyasına buradan baxa bilərsiniz:

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (ümumiyyətlə Union-Find aka Disjoint Set Union üçün istifadə olunur) elementlərin bir-birindən ayrı (üst-üstə düşməyən) dəstlərə bölməsini idarə etmək üçün istifadə edilən məlumat strukturudur. O, iki əsas əməliyyatı səmərəli şəkildə dəstəkləyir:

Tap : Elementin hansı çoxluğa aid olduğunu müəyyən edir.
Birlik : İki dəsti birləşdirir.

Bu struktur Kruskal alqoritmi kimi minimum əhatəli ağac alqoritmlərində xüsusilə faydalıdır.

Məndə təsadüfi labirintlər yaratmaq üçün istifadə olunan Kruskal alqoritminin tətbiqi var və bu, dəstləri səmərəli şəkildə birləşdirmək üçün Disjoint Set-in aşağıdakı PHP tətbiqinə əsaslanır. Əgər maraqlanırsınızsa, onu burada hərəkətdə görə bilərsiniz: Kruskalın Alqoritmi Maze Generatoru

Hər halda, bu mənim Disjoint Set-in PHP tətbiqidir:

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

Əyləncə üçün labirintlər yaratmaqdan başqa, Disjoint Set məlumat strukturu, şübhəsiz ki, real həyat ssenariləri üçün də istifadə edilə bilər.

Təsəvvür edin, məsələn, istifadəçilərinə yeni dostlar təklif etmək istəyən bir sosial şəbəkə və sonra deyək ki, bu dostluq əlaqələri olan altı nəfərimiz var:

1 və 2 dostdur.
2 və 3 dostdur.
4 və 5 dostdur.
6-nın dostu yoxdur.

Birlik-Tap alqoritmini bu ayrı-ayrı qruplara tətbiq edərək, aşağıdakıları tapmalıyıq:

Bir qrupda 1, 2 və 3.
İkinci qrupda 4 və 5.
Üçüncü qrupda 6.

Buna əsaslanaraq, 1 və 3-ün dost olmasını təklif etmək məntiqli olardı, çünki ortaq 2-ci şəxs var.

Əlbəttə ki, bu kimi kiçik bir nümunədə bu faktı özünüz asanlıqla görə bilərsiniz, lakin bu alqoritmin səmərəliliyi onu milyardlarla insana və dost qruplarına mümkün qədər genişləndirməyə imkan verir.