Disjoint Set (Union-Find Algorithm) ing PHP

Diterbitake: 16 Februari 2025 ing 12:29:55 UTC

Artikel iki nampilake implementasi PHP saka struktur data Disjoint Set, sing umum digunakake kanggo Union-Find ing algoritma wit spanning minimal.

Kaca iki diterjemahake mesin saka basa Inggris supaya bisa diakses dening akeh wong. Sayange, terjemahan mesin durung dadi teknologi sing sampurna, mula kesalahan bisa kedadeyan. Yen sampeyan seneng, sampeyan bisa ndeleng versi Inggris asli ing kene:

Disjoint Set (Union-Find Algorithm) in PHP

Set Disjoint (umume digunakake kanggo Union-Find aka Disjoint Set Union) yaiku struktur data sing digunakake kanggo ngatur partisi unsur dadi set sing ora nyambung (ora tumpang tindih). Ndhukung rong operasi utama kanthi efisien:

Temokake : Nemtokake sing nyetel unsur belongs kanggo.
Union : Nggabungake rong set bebarengan.

Struktur iki utamané migunani ing algoritma wit spanning minimal, kayata algoritma Kruskal.

Aku duwe implementasine saka algoritma Kruskal kang digunakake kanggo ngasilaken mazes acak sing gumantung ing ngisor PHP implementasine saka Disjoint Set kanggo irit nggabung set. Yen sampeyan kasengsem, sampeyan bisa ndeleng tumindak ing kene: Generator labirin Algoritma Kruskal

Oalah, iki implementasi PHP saka 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]++;
            }
        }
    }
}

Saliyane ngasilake mazes kanggo seneng-seneng, struktur data Disjoint Set mesthi uga bisa digunakake kanggo skenario nyata.

Bayangake, contone, jaringan sosial sing pengin menehi saran kanca anyar kanggo pangguna, banjur ujar manawa ana enem wong sing duwe hubungan kanca iki:

1 lan 2 iku kanca.
2 lan 3 kanca.
4 lan 5 kanca.
6 ora duwe kanca.

Nglamar algoritma Union-Find menyang grup sing kapisah iki, kita kudu nemokake ing ngisor iki:

1, 2 lan 3 ing siji klompok.
4 lan 5 ing klompok kapindho.
6 ing klompok katelu.

Adhedhasar iki, mesthine kudu menehi saran yen 1 lan 3 kudu dadi kanca, amarga padha duwe wong 2 sing padha.

Mesthi, ing conto cilik kaya iki, sampeyan bisa kanthi gampang ngerteni kasunyatan iki dhewe, nanging efisiensi algoritma iki ngidini sampeyan bisa skala nganti milyaran wong lan klompok kanca.