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

Nəşr olundu: 16 fevral 2025 at 12:34:26 UTC
Son yeniləmə: 26 yanvar 2026 at 10:37:16 UTC

Bu məqalədə minimum spanning tree alqoritmlərində Union-Find üçün geniş 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 və ya Ayrı-ayrı Dəst Birliyi üçün istifadə olunur) elementlərin ayrı-ayrı (üst-üstə düşməyən) çoxluqlara bölünməsini idarə etmək üçün istifadə olunan məlumat strukturudur. O, iki əsas əməliyyatı səmərəli şəkildə dəstəkləyir:

Tap: Elementin hansı dəstəyə aid olduğunu müəyyən edir.
Union: İki dəsti birləşdirir.

Bu struktur xüsusilə Kruskal alqoritmi kimi minimum spanning tree alqoritmlərində faydalıdır.

Məndə Kruskalın təsadüfi labirintlər yaratmaq üçün istifadə olunan alqoritminin tətbiqi var və aşağıdakı PHP Disjoint Set implementasiyasına əsaslanaraq dəstləri səmərəli birləşdirir. Əgər maraqlanırsınızsa, onu burada izləyə bilərsiniz: Kruskalın Alqoritmi Maze Generatoru

Hər halda, bu mənim Disjoint Set-in PHP versiyasıdır:

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

Labirintləri əyləncə üçün yaratmaqla yanaşı, Disjoint Set məlumat strukturu real həyat ssenariləri üçün də istifadə oluna bilər.

Məsələn, təsəvvür edin ki, bir sosial şəbəkə istifadəçilərinə yeni dostlar təklif etmək istəyir və sonra deyək ki, artıq bu dost münasibətləri olan altı nəfər var:

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

Union-Find alqoritmini bu ayrı qruplara tətbiq etsək, aşağıdakıları tapmalıyıq:

1, 2 və 3 bir qrupda.
4 və 5 ikinci qrupda.
6 nəfər üçüncü qrupda.

Buna əsaslanaraq, 1 və 3-ün dost olmasını təklif etmək məntiqlidir, çünki onların 2-ci şəxs ortaq cəhəti var.

Əlbəttə, belə kiçik bir nümunədə bu faktı özünüz asanlıqla görə bilərsiniz, amma bu alqoritmin effektivliyi ona milyardlarla insan və dost qrupuna mümkün miqyaslanmağa imkan verir.