Minimum yayılan ağaç: Prim, Kruskal ve union-find

Bir kampüse kablo çekiyorsun. Her bina çifti arasında bir maliyet var. Bütün binaları birbirine bağlamak istiyorsun ama en az kabloyla. Cevap minimum yayılan ağaçtır (minimum spanning tree, MST): tüm düğümleri içeren, döngüsüz, toplam ağırlığı en küçük kenar kümesi. Bu haftanın iki algoritması da greedy’dir. Sınav ve quiz soruları neredeyse hep iz sorusudur: “Kruskal’ın kabul ettiği kenarları sırayla yaz”, “Prim’i A’dan başlat, sırayı ver”, “MST ağırlığı kaç?”, “union-find dizisini göster”.

Altın kurallar:

1. MST’de tam V − 1 kenar vardır. Daha azı bağlamaz, daha fazlası döngü kurar.
2. Kruskal kenar seçer: en hafif kenardan başla, döngü kurmuyorsa al.
3. Prim düğüm büyütür: tek ağaç, her adımda ona en ucuz bağlanan düğümü ekle.
4. Prim’in tablosu Dijkstra’ya benzer ama yol toplamı tutmaz, sadece tek kenarın ağırlığını tutar.
5. Döngü kontrolü union-find ile yapılır: iki uç aynı kümedeyse red.

Tanım ve iki özellik

Yayılan ağaç (spanning tree): bağlı, yönsüz bir grafın tüm düğümlerini içeren ve döngüsü olmayan alt grafı. V düğüm için V−1 kenar. Minimum olanı, kenar ağırlıkları toplamı en küçük olandır.

Bütün MST algoritmalarının doğruluğu iki özelliğe dayanır:

• Kesim özelliği (cut property): Düğümleri herhangi iki gruba ayır. İki grup arasında geçen kenarlardan en hafifi (eşsizse) her MST’de yer alır.
• Döngü özelliği (cycle property): Bir döngüdeki en ağır kenar (eşsizse) hiçbir MST’de yer almaz.

Prim kesim özelliğini doğrudan kullanır (kesim = ağaç / geri kalanı). Kruskal, reddettiği her kenarın bir döngünün en ağır kenarı olduğunu kullanır.

Çalışma grafı

G grafı (yönsüz). Kenarlar ağırlığa göre sıralı:

kenar  ağırlık      kenar  ağırlık
A-C    1            B-C    7
C-D    2            C-E    8
A-B    3            D-F    9
D-E    4            B-E    10
B-D    5
E-F    6

Kruskal algoritması

1. Kenarları ağırlığa göre artan sırala (eşitlikte listeleme sırası).
2. Her düğüm kendi kümesinde başlar.
3. Sıradaki kenar (u, v): find(u) != find(v) ise kenarı al ve union(u, v). Değilse reddet (döngü kurar).
4. V−1 kenar alınca dur.

kenar  karar   kümeler sonrası
A-C 1  KABUL   {A,C} {B} {D} {E} {F}
C-D 2  KABUL   {A,C,D} {B} {E} {F}
A-B 3  KABUL   {A,B,C,D} {E} {F}
D-E 4  KABUL   {A,B,C,D,E} {F}
B-D 5  RED     B ve D aynı kümede
E-F 6  KABUL   {A,B,C,D,E,F} → 5 kenar, dur

Programın parent dizisi (A..F sırasıyla, her eleman o düğümün ebeveyni):

  A-C 1 ACCEPT parent [A B A D E F]
  C-D 2 ACCEPT parent [A B A A E F]
  A-B 3 ACCEPT parent [A A A A E F]
  D-E 4 ACCEPT parent [A A A A A F]
  B-D 5 reject parent [A A A A A F]
  E-F 6 ACCEPT parent [A A A A A A]
Kruskal total 16 edges 5

MST:

    B
    | 3
    A
    | 1
    C
    | 2
    D
    | 4
    E
    | 6
    F

Bu örnekte MST bir zincir çıktı; her zaman böyle olmaz.

TUZAK · kalan kenarları da kontrol etmeye çalışmak. 5. kenar alındığında dur. B-C 7, C-E 8 gibi kenarlar zaten döngü kurar; sınavda tabloyu gereksiz uzatıp zaman kaybetme. Ama soru “list all rejected edges” diyorsa kalanları da red olarak yaz.

Union-find (disjoint set)

Kruskal’ın döngü kontrolü bu yapıyla hızlanır. Her küme bir ağaçtır; parent[x] x’in ebeveynidir, kökte parent[r] = r.

• find(x): köke kadar çık, kökü döndür.
• union(a, b): iki kökü bul, birini diğerinin altına bağla.

İki iyileştirme:

• Union by size (ya da rank): küçük ağacın kökünü büyüğün altına bağla. Ağaç yüksekliği $O(\log n)$‘i geçmez.
• Path compression: find sırasında yoldaki her düğümü doğrudan köke bağla. Sonraki find’lar tek adım.

İkisi birlikte işlem başına pratikte sabit süre verir ($O(\alpha(n))$, ters Ackermann).

İz: 0..7 üzerinde union by size

Kural: boyutlar eşitse ikinci argümanın kökü birincinin altına girer.

  union(0,1) parent [0, 0, 2, 3, 4, 5, 6, 7]
  union(2,3) parent [0, 0, 2, 2, 4, 5, 6, 7]
  union(4,5) parent [0, 0, 2, 2, 4, 4, 6, 7]
  union(6,7) parent [0, 0, 2, 2, 4, 4, 6, 6]
  union(0,2) parent [0, 0, 0, 2, 4, 4, 6, 6]
  union(4,6) parent [0, 0, 0, 2, 4, 4, 4, 6]
  union(0,4) parent [0, 0, 0, 2, 0, 4, 4, 6]

     önce                 find(7) sonrası
       0                       0
     / | \                / / | \ \
    1  2  4              1 2  4  6 7
       |  | \              |  |
       3  5  6             3  5
             |
             7

  path from 7 before find: 7 6 4 0
  find(7) = 0 parent after [0, 0, 0, 2, 0, 4, 0, 0]

TUZAK · path compression sadece yoldakileri değiştirir. find(7) sonrası 6 ve 7 köke bağlandı. 3 ve 5 yolda değildi, ebeveynleri (2 ve 4) değişmedi.

Prim algoritması

1. Başlangıç düğümünün değeri 0, diğerleri ∞.
2. Ağaçta olmayanlar içinden değeri en küçük düğümü seç, ağaca ekle (eşitlikte küçük etiket).
3. Yeni düğümün her komşusu u için: w(v,u) < d[u] ise d[u] = w(v,u), from[u] = v.
4. Tüm düğümler eklenene kadar tekrar et.

Dijkstra’dan tek fark 3. adımda: Dijkstra d[v] + w karşılaştırır, Prim sadece w. Prim’in d[u] değeri “u’yu ağaca bağlamanın en ucuz kenarı”dır, kaynaktan uzaklık değil.

G’de A’dan başla (* ağaçta):

ekle  A   B   C   D   E   F    kenar
A     0*  3   1   ∞   ∞   ∞    -
C     0*  3   1*  2   8   ∞    A-C 1
D     0*  3   1*  2*  4   9    C-D 2
B     0*  3*  1*  2*  4   9    A-B 3
E     0*  3*  1*  2*  4*  6    D-E 4
F     0*  3*  1*  2*  4*  6*   E-F 6

Prim order A C(via A-C 1) D(via C-D 2) B(via A-B 3) E(via D-E 4) F(via E-F 6) total 16

Aynı MST, farklı ekleme sırası. F’den başlasaydın sıra F, E, D, C, A, B olurdu ama kenarlar ve toplam 16 yine aynı.

İPUCU · Prim mi Kruskal mı? Seyrek grafta ve kenar listesi verildiğinde Kruskal pratiktir. Yoğun grafta (komşuluk matrisi) Prim’in $O(V^2)$ sürümü iyidir. Sınavda hangisi istenirse onun sırasını yaz; ikisini karıştırma.

MST tek mi?

Bütün kenar ağırlıkları farklıysa MST tektir. Eşit ağırlıklar varsa birden fazla MST olabilir, ama hepsinin toplamı aynıdır.

H grafı: P-Q 2, P-R 3, Q-R 2, Q-S 4, R-S 4, R-T 5, S-T 1.

  S-T 1 ACCEPT
  P-Q 2 ACCEPT
  Q-R 2 ACCEPT
  P-R 3 reject
  Q-S 4 ACCEPT
Kruskal total 9 edges 4

Q-S yerine R-S (o da 4) alınsaydı da {P, Q, R} ile {S, T} bağlanırdı ve toplam yine 9 olurdu. İki geçerli MST var.

Quiz provası

Quiz’de genelde 15-20 dakikada tek bir graf verilir ve üç şey istenir. Kendini zamanla dene (G grafı):

1) Kruskal'ın kabul ettiği kenarlar sırayla?
2) Prim B'den başlarsa ekleme sırası?
3) MST ağırlığı?
cevaplar:
1) A-C, C-D, A-B, D-E, E-F
2) B, A(3), C(1), D(2), E(4), F(6)
3) 16

2. cevabın kontrolü: B’den A=3, D=5, C=7, E=10. A eklenir, C=1 olur. C eklenir, D=2, E=8. D eklenir, E=4, F=9. E eklenir, F=6. Kâğıda tabloyu çizmeden yapma; ezbere giden en sık hata, B’den başlayınca D=5’i seçmek.

Karmaşıklık özeti

Sık yapılan hatalar

ekle  A  B  C  D  E  F
A     0* 3  1  ∞  ∞  ∞
C     0* 3  1* 2  8  ∞
D     0* 3  1* 2* 4  9
B     0* 3* 1* 2* 4  9
E     0* 3* 1* 2* 4* 6
F     0* 3* 1* 2* 4* 6*

        0
      / | \
     1  2  4
        |  | \
        3  5  6
              |
              7

static int[] parent, size;
static int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);   // path compression
    return parent[x];
}
static boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;        // aynı küme: döngü
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;                   // küçük, büyüğün altına
    size[ra] += size[rb];
    return true;
}

static int kruskal(int n, int[][] edges) {
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    int[][] es = edges.clone();
    Arrays.sort(es, (x, y) -> Integer.compare(x[2], y[2]));
    int total = 0, used = 0;
    for (int[] e : es) {
        if (union(e[0], e[1])) {
            total += e[2];
            if (++used == n - 1) break;
        }
    }
    return total;
}