Ayrık Kümeler (Union-Find)

#Nasıl çalışır?

Union-Find (ayrık kümeler, disjoint set union), elemanları birbiriyle örtüşmeyen kümelere ayırır ve iki soruyu çok hızlı yanıtlar: iki kümeyi birleştir, iki eleman aynı kümede mi?

Her küme bir ağaç olarak saklanır; her eleman yalnızca ebeveynini bilir ve kök kümenin temsilcisidir. Bütün yapı tek bir parent dizisinde durur.

İki iyileştirme ağaçları neredeyse düz tutar: rank ile birleştirme kısa ağacı uzun olanın altına bağlar, yol sıkıştırma da find sırasında geçilen her düğümü doğrudan köke bağlar.

#Kendin dene

#Temel işlemler

find(x)

Ebeveynleri takip ederek x'in kökünü (temsilcisini) bulur; yol sıkıştırma ile yolu kısaltır.

union(a, b)

a ve b'nin köklerini bulur; farklılarsa düşük rank'li kökü diğerinin altına bağlar.

connected(a, b)

find(a) == find(b) ise iki eleman aynı kümededir.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

class UnionFind:
    def __init__(self, n: int) -> None:
        self._parent = list(range(n))  # every element is its own root
        self._rank = [0] * n  # an upper bound on each tree's height
        self.sets = n

    def find(self, x: int) -> int:
        if self._parent[x] != x:
            self._parent[x] = self.find(self._parent[x])  # path compression
        return self._parent[x]

    def union(self, a: int, b: int) -> None:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return  # already in the same set
        # Union by rank: hang the shorter tree under the taller one.
        if self._rank[ra] < self._rank[rb]:
            ra, rb = rb, ra
        self._parent[rb] = ra
        if self._rank[ra] == self._rank[rb]:
            self._rank[ra] += 1
        self.sets -= 1

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)


uf = UnionFind(8)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
uf.union(5, 6)
show = lambda b: "true" if b else "false"
print(show(uf.connected(0, 2)))  # true
print(show(uf.connected(0, 5)))  # false
print(uf.sets)                   # 4: {0,1,2,3} {4} {5,6} {7}

#Karmaşıklık

α(n), ters Ackermann fonksiyonudur; evrendeki atom sayısı kadar eleman için bile 5'i geçmez. Yani iki iyileştirme birlikte kullanıldığında işlemler pratikte sabit sürelidir. İyileştirmeler olmadan ağaç zincire dönüşebilir ve find O(n) olur.

#Ne zaman kullanılır?

Kruskal ile minimum kapsayan ağaç, bir grafın bağlı bileşenlerini saymak, yönsüz grafta döngü tespiti, ağ bağlantısı soruları ve görüntü işlemede bölge etiketleme union-find kullanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Kruskal Algoritması