Union-Find ve Minimum Spanning Tree: Kruskal ile Ağ Kurmak

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Bookstore'un müşteri tablosunda yıllar içinde birikmiş hesaplar var. Pazarlama ekibi "gerçekte kaç müşterimiz var?" diye soruyor. Kural basit: aynı e-posta ya da aynı telefonu paylaşan hesaplar aynı kişiye ait.

CustomerAccount[] accounts =
[
    new(1, "Ada L.", ["ada@example.com"]),
    new(2, "Ada Lovelace", ["ADA@example.com", "+90 555 000 0001"]),
    new(3, "A. Lovelace", ["+90 555 000 0001", "lovelace@example.org"]),
    new(4, "Grace H.", ["grace@example.com"]),
    new(5, "Grace Hopper", ["+90 555 000 0002"]),
    new(6, "G. Hopper", ["grace@example.com", "+90 555 000 0002"]),
    new(7, "Alan T.", ["alan@example.com"]),
];

Hesap 1 ile hesap 3'ün ortak hiçbir iletişim bilgisi yok. Hesap 4 ile 5'in de. Kaç gerçek müşteri var: 7 mi, 5 mi, 3 mü? Ve bu kontrolü bir milyon hesap için yaparken her yeni eşleşmede "bu iki hesap zaten aynı grupta mı?" sorusunu ne kadar hızlı cevaplayabilirsin?

Union-Find: İki Soruluk Bir Yapı

Union-Find (disjoint set) elemanları birbirinden ayrık gruplara bölen ve yalnız iki işlemi destekleyen bir yapıdır. Find(x): x hangi gruba ait? Union(a, b): a'nın grubuyla b'nin grubunu birleştir. Her grup bir tree olarak tutulur ve tree'nin kökü grubun temsilcisidir; iki elemanın aynı grupta olup olmadığını kökleri karşılaştırarak anlarız. Elemanlar 0..n-1 arası int'lerse bütün yapı tek bir parent array'idir.

En düz implementasyon:

// Compression yok, rank yok: doğru ama uzun zincirlere dönüşebilir
public sealed class NaiveDisjointSet
{
    private readonly int[] _parent;

    public NaiveDisjointSet(int count)
    {
        _parent = new int[count];
        for (int i = 0; i < count; i++) _parent[i] = i;
    }

    public int Find(int x)
    {
        while (_parent[x] != x) x = _parent[x];
        return x;
    }

    public bool Union(int a, int b)
    {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return false;
        _parent[ra] = rb;
        return true;
    }
}

Doğru çalışıyor ama bir zaafı var: Union hangi kökün diğerinin altına gireceğini düşünmüyor. Union(0, 1), Union(1, 2), ... sırasıyla birleştirirsen 0'dan 1'e, 1'den 2'ye uzanan n uzunluğunda bir zincir oluşur ve Find(0) bütün zinciri yürür. Gerçek koşu:

naive: 10,000 Find calls on a 100,000-element chain: 961 ms
rank + compression: 10,000 Find calls: 0.06 ms

İkinci satırdaki fark iki küçük fikirden geliyor.

Path Compression ve Union by Rank

Union by rank: birleştirirken kısa tree'yi uzun olanın altına as. Rank, tree yüksekliğinin bir üst sınırıdır; eşit rank'lı iki tree birleşince yeni kökün rank'ı bir artar. Bu tek başına yüksekliği O(log n) ile sınırlar. Path compression: Find kökü bulduktan sonra yol üzerindeki her elemanı doğrudan köke bağla; aynı yol bir daha yürünmez.

public sealed class DisjointSet
{
    private readonly int[] _parent;
    private readonly byte[] _rank;

    public DisjointSet(int count)
    {
        _parent = new int[count];
        _rank = new byte[count];
        for (int i = 0; i < count; i++) _parent[i] = i;
        Count = count;
    }

    public int Count { get; private set; }   // ayrık küme sayısı

    public int Find(int x)
    {
        int root = x;
        while (_parent[root] != root) root = _parent[root];

        // Path compression: yoldaki her node'u doğrudan köke bağla
        while (_parent[x] != root)
        {
            int next = _parent[x];
            _parent[x] = root;
            x = next;
        }

        return root;
    }

    public bool Union(int a, int b)
    {
        int ra = Find(a), rb = Find(b);
        if (ra == rb)
        {
            return false;
        }

        // Union by rank: kısa tree uzun olanın altına asılır
        if (_rank[ra] < _rank[rb]) (ra, rb) = (rb, ra);
        _parent[rb] = ra;
        if (_rank[ra] == _rank[rb]) _rank[ra]++;
        Count--;
        return true;
    }

    public bool Connected(int a, int b) => Find(a) == Find(b);
}

Find'ı bilinçli olarak iki geçişli ve iterative yazdık: ilk döngü kökü bulur, ikincisi yolu sıkıştırır. Recursive yazım daha kısadır (return _parent[x] = Find(_parent[x]);) ama sıkıştırma öncesi ilk çağrıda zincir uzunsa, örneğin naive bir yapıdan veri taşıyorsan, recursion derinliği n olur. Rank byte, çünkü union by rank ile rank hiçbir zaman log₂ n'i geçemez; 2⁶⁴ eleman için bile 64.

İki teknik birlikte kullanıldığında m işlemin toplam maliyeti O(m·α(n)) olur; α ters Ackermann fonksiyonu, evrendeki atom sayısı kadar n için bile 5'i geçmez. Pratikte her işlem sabit maliyetli. Bu "tek tek pahalı olabilir ama toplamda ucuz" türünden bir garanti, yani amortized; ne anlama geldiğini Big-O ve Complexity serisinin "Amortized Analysis: List<T>.Add Neden O(1) Sayılır" yazısında anlattık. İspatı Tarjan'ın 1975 tarihli analizine dayanır ve bu yazının kapsamı dışında.

Testte optimize versiyonu naive olanla rastgele işlemler üzerinde karşılaştırıyoruz: hız farklı, cevaplar aynı olmalı.

[Fact]
public void Naive_GivesSameAnswersAsOptimized()
{
    Random random = new(11);
    DisjointSet fast = new(500);
    NaiveDisjointSet naive = new(500);
    for (int i = 0; i < 400; i++)
    {
        int a = random.Next(500), b = random.Next(500);
        Assert.Equal(naive.Union(a, b), fast.Union(a, b));
    }

    for (int i = 0; i < 1_000; i++)
    {
        int a = random.Next(500), b = random.Next(500);
        Assert.Equal(naive.Find(a) == naive.Find(b), fast.Connected(a, b));
    }
}

Duplicate Müşteri Hesaplarını Birleştirmek

Açılıştaki probleme dönelim. Her hesap bir eleman. Her iletişim bilgisinin (e-posta ya da telefon) ilk görüldüğü hesabı bir dictionary'de tutuyoruz; aynı bilgi başka bir hesapta yeniden görülürse iki hesabı birleştiriyoruz:

public sealed record CustomerAccount(int Id, string Name, string[] Contacts);

public static class AccountMerger
{
    // Herhangi bir e-posta ya da telefonu paylaşan hesaplar aynı gruba düşer
    public static List<List<CustomerAccount>> Merge(IReadOnlyList<CustomerAccount> accounts)
    {
        DisjointSet sets = new(accounts.Count);
        Dictionary<string, int> firstOwner = new(StringComparer.OrdinalIgnoreCase);
        for (int i = 0; i < accounts.Count; i++)
        {
            foreach (string contact in accounts[i].Contacts)
            {
                if (!firstOwner.TryAdd(contact, i))
                {
                    sets.Union(i, firstOwner[contact]);
                }
            }
        }

        return [.. Enumerable.Range(0, accounts.Count)
            .GroupBy(sets.Find)
            .Select(g => g.Select(i => accounts[i]).ToList())];
    }
}

[1, 2, 3] Ada L. | Ada Lovelace | A. Lovelace
[4, 5, 6] Grace H. | Grace Hopper | G. Hopper
[7] Alan T.

Cevap 3. Hesap 1 ile 3'ün ortak bilgisi yok ama ikisi de hesap 2 üzerinden bağlı: 1 ile 2 aynı e-postayı (büyük/küçük harf farkıyla), 2 ile 3 aynı telefonu paylaşıyor. Union-Find bu geçişliliği kendiliğinden yakalar. Hesap 5 ve 6 için de aynısı. Toplam maliyet, iletişim bilgisi sayısı k için yaklaşık O(k·α(n)), yani pratikte doğrusal.

Aynı soruyu serinin 15. yazısındaki gibi bir graph kurup connected component'leri BFS (Breadth-First Search) ile bularak da cevaplayabilirdik. Fark, Union-Find'ın artımlı (incremental) çalışması: yeni bir hesap kaydolduğunda ya da bir müşteri telefonunu güncellediğinde graph'ı yeniden gezmeden tek bir Union ile grupları güncellersin. Bir kısıtı da var: Union-Find birleştirmeyi geri alamaz. "Bu iki hesap yanlışlıkla birleşti, ayır" işlemi yoktur; ya baştan kurarsın ya da birleştirme kararlarını ayrı bir kayıtta tutarsın.

Minimum Spanning Tree ve Kruskal

İkinci klasik kullanım. Bookstore yedi şehirdeki ofislerini fiber ile birbirine bağlayacak. Her olası hattın bir kurulum maliyeti var (birim, örnek değerler). Her ofisin diğerlerine (doğrudan ya da dolaylı) ulaşabildiği en ucuz hat kümesi hangisi? Bu bir MST (Minimum Spanning Tree): V vertex'i bağlayan, V - 1 edge'li ve toplam ağırlığı en küçük tree.

Kruskal algoritması (1956) açgözlü bir kural uygular: edge'leri ucuzdan pahalıya sırala, her edge'i sırayla dene ve iki ucu zaten bağlı değilse al. "Zaten bağlı mı" sorusu tam olarak Union-Find'ın işi: Union iki uç farklı gruptaysa birleştirip true, aynı gruptaysa (yani edge bir cycle kapatacaksa) false döner.

public sealed record Link(string From, string To, int Cost);

// Kruskal: önce en ucuz edge'ler, cycle kapatacak edge atlanır. O(E log E).
public static List<Link> Kruskal(IReadOnlyList<string> sites, IEnumerable<Link> links)
{
    Dictionary<string, int> index = sites.Select((s, i) => (s, i)).ToDictionary(x => x.s, x => x.i);
    DisjointSet sets = new(sites.Count);
    List<Link> tree = [];
    foreach (Link link in links.OrderBy(l => l.Cost))
    {
        if (sets.Union(index[link.From], index[link.To]))
        {
            tree.Add(link);
            if (tree.Count == sites.Count - 1) break;
        }
    }

    return tree;
}

string[] sites = ["Istanbul", "Ankara", "Izmir", "Bursa", "Antalya", "Konya", "Eskisehir"];
Link[] links =
[
    new("Istanbul", "Bursa", 3), new("Istanbul", "Eskisehir", 6), new("Istanbul", "Ankara", 9),
    new("Bursa", "Eskisehir", 3), new("Bursa", "Izmir", 5), new("Eskisehir", "Ankara", 4),
    new("Eskisehir", "Konya", 6), new("Ankara", "Konya", 4), new("Izmir", "Antalya", 8),
    new("Konya", "Antalya", 5), new("Izmir", "Eskisehir", 7),
];

  Istanbul - Bursa: 3
  Bursa - Eskisehir: 3
  Eskisehir - Ankara: 4
  Ankara - Konya: 4
  Bursa - Izmir: 5
  Konya - Antalya: 5
Kruskal total=24, links=6; Prim total=24; all links total=60

11 olası hattın toplamı 60 birim; MST 6 hatla 24 birimde yedi ofisi bağlıyor. Altıncı hat eklenince döngü break ile bitiyor; Istanbul - Eskisehir (6) ve daha pahalı hatlara hiç bakılmıyor. Bakılsaydı da atlanırdı: İstanbul ve Eskişehir Bursa üzerinden zaten bağlı, o hattı almak bir cycle kapatırdı. Maliyetin büyük kısmı sıralamada: O(E log E). Union-Find işlemleri neredeyse bedava.

MST'nin bir uyarısı: iki ofis arasındaki yol tree üzerinden gider ve en kısa yol olmak zorunda değildir. Antalya'dan İzmir'e MST'de Konya, Ankara, Eskişehir, Bursa üzerinden 5 + 4 + 4 + 3 + 5 = 21 birimlik bir yol var, doğrudan hat 8 birimken. MST "toplam kurulum maliyeti en düşük ağ"ı verir; "her iki nokta arası en hızlı"yı değil. O ikinci soru bir önceki yazının, Dijkstra'nın konusu.

Prim'e Kısa Bakış

Prim algoritması aynı sonuca farklı yoldan varır: tek bir ofisten başlar ve her adımda ağa bağlı olanlarla olmayanlar arasındaki en ucuz hattı ekler. "En ucuz aday hat" sorusu bir PriorityQueue ile cevaplanır; serinin 17. yazısındaki gibi lazy deletion kullanırız: iki ucu da ağdaysa atla.

// Prim: bir başlangıç ofisinden ağı PriorityQueue ile büyüt. O(E log V).
public static List<Link> Prim(IReadOnlyList<string> sites, IReadOnlyList<Link> links)
{
    Dictionary<string, List<Link>> adjacent = sites.ToDictionary(s => s, _ => new List<Link>());
    foreach (Link l in links)
    {
        adjacent[l.From].Add(l);
        adjacent[l.To].Add(new Link(l.To, l.From, l.Cost));
    }

    HashSet<string> inTree = [sites[0]];
    PriorityQueue<Link, int> frontier = new();
    foreach (Link l in adjacent[sites[0]]) frontier.Enqueue(l, l.Cost);
    List<Link> tree = [];
    while (tree.Count < sites.Count - 1 && frontier.TryDequeue(out Link? link, out _))
    {
        if (!inTree.Add(link.To)) continue; // iki uç da zaten bağlı
        tree.Add(link);
        foreach (Link next in adjacent[link.To])
        {
            if (!inTree.Contains(next.To)) frontier.Enqueue(next, next.Cost);
        }
    }

    return tree;
}

İkisi de aynı toplamı, 24'ü buluyor. Eşit ağırlıklı edge'ler varsa farklı ama eşit maliyetli tree'ler seçebilirler; testte bu yüzden hatların kendisini değil toplam maliyeti karşılaştırıyoruz. Kaba kural: edge listesi zaten elindeyse ve graph seyrekse Kruskal, graph yoğunsa ya da adjacency list olarak duruyorsa Prim.

Test run summary: Passed!
  total: 4
  failed: 0
  succeeded: 4
  skipped: 0
  duration: 269ms

Ölçüm: Naive ve Optimize Union-Find

20.000 elemanı komşularıyla birleştirip uzun bir zincir kurdum, sonra her elemanın kökünü sordum:

[Benchmark(Baseline = true)]
public long Naive()
{
    NaiveDisjointSet sets = new(N);
    for (int i = 0; i < N - 1; i++) sets.Union(i, i + 1);
    long sum = 0;
    for (int i = 0; i < N; i++) sum += sets.Find(i);
    return sum;
}

[Benchmark]
public long RankAndCompression()
{
    DisjointSet sets = new(N);
    for (int i = 0; i < N - 1; i++) sets.Union(i, i + 1);
    long sum = 0;
    for (int i = 0; i < N; i++) sum += sets.Find(i);
    return sum;
}

Ölçümler Apple M5 (10 çekirdek), macOS 27.0.1, .NET 10.0.13, BenchmarkDotNet 0.15.8 ile alındı. Benchmark'ları tek tek çalıştırdım ama makinede paralel işler vardı; mutlak sayılara değil oranlara bak (naive satırının yüksek standart sapması da bundan).

| Method             | N     | Mean          | Ratio | Allocated |
|------------------- |------ |--------------:|------:|----------:|
| Naive              | 20000 | 199,971.00 us | 1.017 |  78.15 KB |
| RankAndCompression | 20000 |      46.09 us | 0.000 |   97.7 KB |

200 ms'ye karşı 46 µs, yaklaşık 4.300 kat. Naive versiyon n²/2 = 200 milyon adım yürüyor; optimize versiyon zinciri hiç oluşturmuyor, çünkü union by rank her yeni elemanı mevcut kökün altına asıyor ve tree'nin yüksekliği 1'de kalıyor. Ratio sütunundaki 0.000, oranın üç basamağa sığmayacak kadar küçük olmasından. Allocation farkı _rank array'inden (20.000 byte).

Üretimde Dikkat

Birleştirme kuralı algoritmadan önemlidir. Union-Find "aynı e-posta" dediğin her şeyi körü körüne birleştirir. E-postaları küçük harfe çevirmeden ve telefonları tek bir biçime (örneğin uluslararası E.164 formatı) getirmeden birleştirirsen gerçek duplicate'leri kaçırırsın. Tersine, "info@" gibi paylaşılan kurumsal adresler ya da bir çağrı merkezinin numarası yüzlerce farklı müşteriyi tek bir dev gruba yapıştırır. Gerçek sistemlerde çok büyük çıkan grupları otomatik birleştirmek yerine incelemeye düşürmek ve hangi bilginin birleştirmeye yol açtığını kaydetmek gerekir.

Union geri alınamaz. Yanlış bir birleştirme kararını düzeltmek için ya bütün yapıyı kalan kurallarla baştan kurarsın (n ve k için doğrusal maliyet, genelde kabul edilebilir) ya da birleştirmeleri bir log olarak saklayıp yeniden oynatırsın. Müşteri verisinde kararı veren her eşleşmeyi saklamak denetim açısından da şarttır.

String id'leri int'e eşle. DisjointSet int index'lerle çalışıyor; müşteri id'leri Guid ise bir Dictionary<Guid, int> ile 0..n-1'e eşlemek, array tabanlı yapıyı korumanın en basit yolu. Serinin 15. yazısındaki id mapping fikrinin aynısı.

Ağ tasarımında MST başlangıç noktasıdır. Tek bir hattın kopması MST'yi ikiye böler, çünkü tree'de yedek yol yoktur. Gerçek bir ağda MST'nin üstüne bilinçli olarak yedek hatlar eklenir; algoritma "en ucuz bağlı ağ"ı verir, "dayanıklı ağ"ı değil.

Sık Düşülen Tuzaklar

Path compression'sız implementasyonun uzun zincirlerde yavaşlaması. Küçük testlerde naive versiyon da hızlı görünür; sorun ancak gerçek veri belirli bir sırayla geldiğinde (artan id'ler, alfabetik liste) ortaya çıkar. Ölçümdeki 4.300 kat bunun bedeli.

Kökler yerine elemanları bağlamak. _parent[a] = b yazmak (kökleri bulmadan) a'nın eski grubunu koparır; a'nın altındaki elemanlar b'nin grubuna geçmez. Union her zaman kökler üzerinde çalışmalı.

_parent[x]'i kök sanmak. Path compression tembeldir; Find çağrılmadan önce _parent[x] kök olmayabilir. Grupları listelerken _parent array'ini doğrudan gruplamak yanlış sonuç verir; GroupBy(sets.Find) gibi her eleman için Find çağır.

Bağlı olmayan graph'ta MST beklemek. Bazı ofisler arasında hiç hat yoksa Kruskal V - 1'den az edge döndürür: bir spanning forest. tree.Count == sites.Count - 1 kontrolü yapmadan sonucu "bütün ofisler bağlandı" diye raporlama.

Küçük Bir Deneme

★☆☆ DisjointSet'e her grubun eleman sayısını tutan bir Size(int x) ekle (union by rank yerine union by size da kullanabilirsin). Account merging örneğinde en büyük grubun boyutunu yazdır.

★★☆ Hesap birleştirmeye bir güvenlik kuralı ekle: bir iletişim bilgisi 10'dan fazla hesapta geçiyorsa birleştirme için kullanılmasın ve "inceleme gerekli" listesine düşsün. Rastgele üretilmiş 100.000 hesaplık bir veriyle test et.

★★★ Bir ağdaki "kritik hatları" bul: MST'deki her hat için, o hat kullanılamazsa yeni MST'nin maliyeti ne kadar artar? Önce her hat için Kruskal'ı yeniden çalıştıran basit versiyonu yaz, sonra bunu daha az iş yapacak şekilde iyileştirmeyi dene.

Graph bloğunu bitirdik: gezinme, sıralama, en kısa yol ve en ucuz ağ. Bundan sonraki yazılar veri yapısından çok problem çözme yöntemlerine odaklanıyor. İlk durak backtracking: bütün olasılıkları sistemli biçimde denemek, ama umutsuz dalları erkenden budayarak. Permutation, subset, N-Queens ve Sudoku ile başlıyoruz.