Union-Find

Ayrık Küme Birleşimi

Okunuşu: yunyın faynd

Güncellendi 3 Ekim 20262 dk okuma

Kısaca

Union-find (ayrık küme birleşimi), öğe gruplarını izleyip birleştiren ve iki öğenin bağlı olup olmadığını neredeyse anında söyleyen veri yapısıdır.

Union-find nedir?

İki işlemi destekler. find(x), x'in ait olduğu grubun bir temsilcisini, yani kökünü döndürür; böylece iki öğe tam olarak kökleri eşit olduğunda aynı gruptadır. union(a, b) ise bir kökü diğerine yönlendirerek a ile b'nin gruplarını birleştirir. İçeride her öğe yalnızca ebeveynini saklar ve küçük ağaçlardan oluşan bir orman oluşturur.

İki basit numara onu son derece hızlı yapar. Yol sıkıştırma (path compression), find sırasında ziyaret edilen her öğenin doğrudan kökü göstermesini sağlayarak ağacı düzleştirir. Ranka ya da boyuta göre birleştirme (union by rank/size) her zaman küçük ağacı büyüğün altına bağlar. Birlikte, her işlemin amortize süresini o kadar yavaş büyüyen, ters Ackermann fonksiyonu kadar bir değere indirirler ki herhangi bir gerçek girdi için pratikte sabittir.

Union-find, bağlantıların zamanla eklendiği ve şeylerin bağlı olup olmadığını sormanız gereken her durumda parlar. Kruskal algoritması onu minimum yayılan ağaç kurmak için kullanır; bir graftaki ya da adalardan oluşan bir ızgaradaki bağlı bileşenleri sayar, kenarlar eklenirken döngüleri tespit eder, bir e-postayı ya da telefon numarasını paylaşan mükerrer hesapları gruplar ve ağ bağlantısını kontrol eder.

Sık yapılan bir yanlış, union-find'ın grupları bölebileceğini de düşünmektir. Yalnızca birleştirmek için tasarlanmıştır; bir bağlantıyı kaldırmak ya da bir grubun bütün üyelerini verimli şekilde listelemek farklı bir yapı gerektirir. Bağlantılar ortadan kalkabiliyorsa BFS gibi graf aramaları ya da daha gelişmiş dinamik bağlantı yapıları gerekir.

Önemli noktalar

Union-find, hangi öğelerin aynı gruba ait olduğunu izler.
find bir grubun kökünü döndürür; union iki grubu birleştirir.
Yol sıkıştırma ve ranka göre birleştirme işlemleri neredeyse O(1) yapar.
Kruskal algoritması, döngü tespiti ve bağlı bileşenler onu kullanır.
Grupları birleştirir ama bölemez.

Örnek

Yol sıkıştırma ve boyuta göre birleştirmeli union-find (Python)python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression (halving)
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                      # already connected: this edge makes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                  # attach the smaller tree under the larger
        self.size[ra] += self.size[rb]
        return True

uf = UnionFind(5)
uf.union(0, 1); uf.union(3, 4)
print(uf.find(1) == uf.find(0), uf.find(1) == uf.find(3))   # True False

Sık sorulan sorular

Union-find ne için kullanılır?

Bağlantılar eklendikçe öğeleri gruplamak ve bağlantı sorularını yanıtlamak için: Kruskal'ın minimum yayılan ağacı, yönsüz graflarda döngü tespiti, bağlı bileşenleri saymak, kümeleme ve mükerrer kayıtları birleştirmek.

Yol sıkıştırma (path compression) nedir?

find içinde, ziyaret edilen her öğenin doğrudan kökü göstermesini sağlayan bir optimizasyondur; böylece o öğeler üzerindeki sonraki aramalar neredeyse anında olur.

Union-find'ın zaman karmaşıklığı nedir?

Yol sıkıştırma ve ranka ya da boyuta göre birleştirmeyle her işlem amortize O(α(n)) zaman alır; burada α, herhangi bir pratik girdi boyutu için en fazla 4 olan ters Ackermann fonksiyonudur.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin