Disjoint Set (Union-Find Algorithm) во PHP

Објавено: 5 март 2025, во 19:55:26 UTC
Последно ажурирано: 26 јануари 2026, во 10:37:19 UTC

Овој напис содржи PHP имплементација на структурата на податоци Disjoint Set, која често се користи за Union-Find во алгоритми со минимално spanning дрво.

Оваа страница беше машински преведена од англиски за да биде достапна за што повеќе луѓе. За жал, машинското преведување сè уште не е усовршена технологија, така што може да се појават грешки. Ако сакате, можете да ја видите оригиналната англиска верзија овде:

Disjoint Set (Union-Find Algorithm) in PHP

Дисјунктниот сет (често користен за Union-Find, познат и како Ununion на неспојни множества) е структура на податоци која се користи за управување со партиција на елементи во дисјунктни (непреклопувачи) множества. Ефикасно поддржува две клучни операции:

Find: Одредува на кој сет припаѓа елементот.
Унија: Спојува два сета.

Оваа структура е особено корисна во алгоритми со минимално опфаќачко дрво, како што е алгоритмот на Крускал.

Имам имплементација на алгоритамот на Крускал кој се користи за генерирање случајни лавиринти и се потпира на PHP имплементацијата на Disjoint Set подолу за ефикасно спојување на сетови. Ако сте заинтересирани, можете да го видите во акција тука: Крускалов алгоритамски генератор на лавиринт

Сепак, ова е мојата 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 нема пријатели.

Применувајќи го алгоритмот Union-Find на овие одделни групи, треба да ги најдеме следниве:

1, 2 и 3 во една група.
4 и 5 во втора група.
6 во трета група.

Врз основа на ова, има смисла да се предложи дека 1 и 3 треба да станат пријатели, бидејќи имаат заедничка личност 2.

Секако, во мал пример како овој, лесно можете сами да го забележите овој факт, но ефикасноста на овој алгоритам му овозможува реално да се скалира на милијарди луѓе и пријателски групи.