Union–Find

OYUNLARDA YAPAY ZEKÂ · ALGORİTMALAR

Union–Find

Dynamic connectivity — “bu ikisi bağlı mı?” sorusunu ışık hızında cevaplamak

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

Problem: dinamik bağlantı — ne soruyoruz? dynamic connectivity
Quick-find: hızlı soru, yavaş birleştirme
Quick-union: hızlı birleştirme… ama ağaçlar uzarsa?
Ağırlıklandırma: küçük ağacı büyüğün altına koy weighted
Yol sıkıştırma: neredeyse sabit zaman path compression
Uygulamalar: labirent üretimi, perkolasyon, Go taş grupları
⚙️ Perde arkası: nesne yok, sadece tamsayı dizileri

🎮 Bu dersin sonunda…

…bir oyunda her seferinde farklı ama her zaman çözülebilir labirentler üretebilecek ve “bu ikisi bağlı mı?” sorusunu milyonlarca nesne için bile anında cevaplayabileceksiniz.

🤔 ISINMA: ZİNDAN KAPILARI

Bir zindanda 10.000 oda var. Oyuncular kapıları birer birer açıyor.

Her kapı açıldıktan sonra soru: “Giriş ile hazine odası arasında artık bir yol var mı?”

Her seferinde tüm haritayı baştan mı tarayacağız? 10.000 kapı × 10.000 oda = 100 milyon adım… 😩

Bugünkü kahramanımız bu soruyu neredeyse tek adımda cevaplıyor: union–find.

Oyunlarda union–find

🌀

Labirent üretimiHer seferinde farklı, her zaman tam bir çözümü olan labirentler

🏝️

Bölge tespitiProsedürel haritada adalar, mağaralar: tüm odalar bağlı mı?

⚫

Taş gruplarıGo, eşleştirme oyunları (match-3), balon patlatma

🏗️

Yıkılabilir yapılarBu parça hâlâ zemine bağlı mı, yoksa düşmeli mi?

🛡️

Klanlar ve ağlarOyuncu grupları birleşince aynı ittifakta mıyız?

🌲

Minimum yayılan ağaçKruskal algoritmasının kalbi (graflar dersi)

Mini sözlük

union(p, q)	birleştir	p ile q arasına bağlantı ekle
find(p)	bul	p’nin bileşeninin “temsilcisi” (kök) kim?
connected(p, q)	bağlı mı?	p’den q’ya bir yol var mı? → `find(p) == find(q)`
connected component	bağlı bileşen	Birbirine bağlı nesnelerin en büyük grubu
root / parent	kök / ebeveyn	Ağacın tepesi / bir üstteki düğüm
weighted	ağırlıklı	Birleştirirken ağaç boyutlarını dikkate almak
path compression	yol sıkıştırma	find sırasında ağacı düzleştirmek
percolation	perkolasyon (sızma)	Bir malzemenin bir ucundan diğerine geçiş olması

LEVEL 0

Dinamik Bağlantı

dynamic connectivity — bağlantılar zamanla geliyor, sorular araya karışıyor

problem: dinamik bağlantı
quick-find
quick-union
ağırlıklandırma
yol sıkıştırma
uygulamalar
perde arkası

Problem

N nesne var: 0, 1, 2, …, N−1 (odalar, piksel, oyuncu…).

union(p, q): p ile q arasına bağlantı ekle
connected(p, q): p ile q arasında (doğrudan ya da dolaylı) yol var mı?

“Bağlı olmak” şu kurallara uyar:

herkes kendisine bağlıdır
p, q’ya bağlıysa q da p’ye bağlıdır
p–q ve q–r bağlıysa p–r de bağlıdır (dolaylı yol!)

Bu kurallar bize nesneleri bağlı bileşenlere ayırmamızı sağlar: aynı bileşendekiler bağlı, farklıdakiler değil.

🎒 Neden sayılar?Nesneleri 0…N−1 diye numaralarsak dizi indeksi olarak kullanabiliriz → çok hızlı. Gerçek oyunda oda adlarını sayılara bir sözlükle (Dictionary<string, int>) çeviririz.

Dene: bağla ve sor

API: sözleşme

Bugün bu sınıfın içini dört farklı şekilde yazacağız ve hızlarını karşılaştıracağız. Kullanan kod hiç değişmeyecek (soyutlama!).

🎬 Ara: union-find’a giriş

Union Find Introduction
WilliamFiset · 5 dk 46 sn · YouTube’da aç

Bu sunumun başından sonuna kuracağımız yapının kısa ve görsel bir haritası: kümeler, kökler, union ve find. Sonraki slaytlardaki her sürüm bu fikrin bir iyileştirmesi.

🤔 İzlerkenVideodaki örnekte hangi iki küme birleşiyor ve yeni kök hangisi oluyor? find işlemi bir elemanın kümesini nasıl buluyor?

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

📊 Union–find (ayrık kümeler)

VisuAlgo (NUS)

Birleştirme ve yol sıkıştırmanın ağaç üzerinde ne yaptığını gösterir.

🔗 Maze Algorithms

Jamis Buck

Labirent üreten on iki algoritmayı (Kruskal, Prim, geri izleme…) yan yana, canlı izleyin.

🔗 Data Structure Visualizations

David Galles (USF)

Neredeyse her veri yapısı için bir oyun alanı: ekle, sil, ara düğmeleriyle yapının nasıl değiştiğini izleyin.

Quiz 1 · problem

10 nesne (0–9) ile başlıyoruz. Şu bağlantılar ekleniyor: 0–1, 2–3, 1–3, 4–5, 0–2. Kaç bileşen kalır?

{0,1,2,3} (0–2 zaten 0–1–3–2 yoluyla bağlıydı, yeni bileşen birleştirmedi), {4,5}, {6}, {7}, {8}, {9} → 6. Her “gerçek” birleştirme bileşen sayısını 1 azaltır: 10 − 4 = 6.

LEVEL 1

Quick-Find

hızlı soru, yavaş birleştirme

problem: dinamik bağlantı
quick-find
quick-union
ağırlıklandırma
yol sıkıştırma
uygulamalar
perde arkası

Fikir: herkesin üzerinde bileşen numarası yazsın

id[i] = i’nin bileşen numarası
connected(p, q): id[p] == id[q] mi? → 2 erişim, süper hızlı ⚡
union(p, q): id’si id[p] olan herkesi id[q] yap → tüm diziyi tara 🐌

🎮 BenzetmeHer oyuncunun tişörtünde takım rengi yazıyor. “Aynı takımda mıyız?” → tişörtlere bak. Ama iki takım birleşince bir takımın bütün oyuncularının tişörtünü değiştirmek gerekir!

Quick-find — animasyon

Quick-find — kod

🎒 list(range(n)) / Array.from({ length: n }, (_, i) => i): “0’dan n−1’e kadar sayılardan oluşan liste”. İkincisi modern JS yazımı; geleneksel hali: boş dizi + for ile push(i).

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`id[i]`	i’nin grup numarası	aynı gruptakiler aynı numarayı taşır
`connected`	iki numarayı karşılaştır	tek adım: sorgu çok hızlı
`for (i …) if (id[i] === pid)`	p’nin grubundaki herkesi q’nun grubuna taşı	her birleştirme bütün diziyi tarar: ~N iş; N birleştirme ~N²
`pid` ve `qid` önceden okunur	döngü sırasında `id[p]` değişir	döngüde `id[p]` kullanılırsa yarıda yanlış gruba geçilir (klasik hata)
`count--`	grup sayısı bir azaldı	“kaç ada kaldı?” sorusunun cevabı

Quiz 2 · quick-find

1 milyon nesne ve 1 milyon union işlemi. Quick-find kabaca kaç dizi erişimi yapar?

Her union tüm diziyi (10⁶) tarar; 10⁶ union × 10⁶ = 10¹². Saniyede 10⁹ işlemle bile ~17 dakika — ve gerçek problemler (sosyal ağlar, büyük haritalar) bundan çok daha büyük. Uyarı: karesel algoritmalar büyümez (bilgisayarlar hızlandıkça problemler de büyür).

LEVEL 2

Quick-Union

tembel yaklaşım: sadece kökleri bağla

problem: dinamik bağlantı
quick-find
quick-union
ağırlıklandırma
yol sıkıştırma
uygulamalar
perde arkası

🎒 Ön bilgi: bir diziyle ağaç çizmek parent array

Ağaçlar dersinde düğümleri nesnelerle ve left/right referanslarıyla bağlamıştık. Burada daha basit bir yol var:

id[i] = i’nin ebeveyninin numarası
Kök: kendini gösteren düğüm (id[r] == r)
Kökü bulmak: ebeveyne çıkmaya devam et:

while p != id[p]:
    p = id[p]

Fikir: kökü kökün altına bağla

find(p): p’nin kökünü bul (ebeveyne çıka çıka)
connected(p, q): kökler aynı mı?
union(p, q): p’nin kökünü, q’nun köküne bağla → tek bir dizi değeri değişir!

😬 Ama…Ağaçlar uzun ve ince olabilir. O zaman find çok yavaş: en kötü N adım. “😈 Kötü sıra” düğmesini deneyin!

Quick-union — animasyon

Quick-union — kod

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`id[i]`	i’nin ebeveyni (kök kendini gösterir)	grup bir ağaçtır; kimlik kökün numarası
`find` döngüsü	köke kadar ebeveyn ebeveyn çık	maliyet = ağacın yüksekliği
`id[i] = j`	bir kökü öbür köke bağla	birleştirme tek atama; ama kötü sırada ağaç zincire döner
`if (i === j) return`	zaten aynı ağaçta	aynı kökü kendine bağlamak döngü yaratırdı
en kötü durum	~N yükseklik	sonraki iyileştirme: küçüğü büyüğün altına (ağırlıklı)

Quiz 3 · quick-union

Quick-union’da union(0,1), union(0,2), …, union(0,N−1) sırasıyla yapılırsa ağacın yüksekliği ne olur?

Her seferinde 0’ın kökü yeni gelenin altına bağlanır: 0→1, sonra (kök 1)→2, sonra (kök 2)→3… Tek kollu bir zincir oluşur: yükseklik N−1. Sonrasında find(0) N adım sürer. Quick-union’ın zayıf noktası: ağacın şeklini hiç düşünmüyor.

🧪 Kod laboratuvarı: find yaz

Laboratuvar senin find’ını kullanarak quick-union yapıyor (parent[find(p)] = find(q)) ve bağlantı sorularının cevaplarını kontrol ediyor. Tablodaki “en derin ağaç” sütununa da bak: “kötü sıra” testinde neden bu kadar derin?

LEVEL 3

Ağırlıklandırma

weighted quick-union — küçük ağaç, büyüğün altına

problem: dinamik bağlantı
quick-find
quick-union
ağırlıklandırma
yol sıkıştırma
uygulamalar
perde arkası

Fikir: küçük ağacı büyüğün altına koy

Her kök için ağacındaki düğüm sayısını tut: sz[]
Birleştirirken küçük ağacın kökünü büyük ağacın köküne bağla
Böylece uzun zincirler oluşamaz

🎮 Benzetmeİki klan birleşiyor: 3 kişilik klan 300 kişilik klanın bayrağı altına girer, tersi değil. Değişmesi gereken “adres” sayısı az olur.

Ağırlıklı quick-union — animasyon

Ağırlıklı quick-union — kod (sadece birkaç satır fark)

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`sz[i]`	i köküne bağlı ağaçtaki düğüm sayısı	yalnızca köklerin sz’si anlamlı
`if (sz[i] < sz[j])`	küçük ağacı büyüğün altına bağla	küçük ağaçtaki her düğümün derinliği 1 artar ama ağaç en az iki katına çıkar
`sz[j] += sz[i]`	birleşen ağacın boyunu güncelle	sonraki birleşmelerde doğru karşılaştırma için
sonuç	yükseklik en çok lg N	bir düğüm en çok lg N kez “iki katı büyük” bir ağaca katılabilir

📐 Neden hızlı? Derinlik en fazla lg N

Bir x düğümünün derinliği ne zaman artar? Sadece x’in ağacı, kendisinden büyük ya da eşit bir ağacın altına girdiğinde.

O anda x’in içinde bulunduğu ağacın boyutu en az iki katına çıkar.

1 düğümden başlayıp kaç kez iki katına çıkabilir? N’e ulaşana kadar: en fazla lg N kez. (Arama dersindeki “kaç kez yarıya?” sorusunun tersi!)

ÖnermeAğırlıklı quick-union’da N düğümlü bir ağaçta her düğümün derinliği en fazla lg N’dir. Dolayısıyla find, union ve connected en kötü durumda ~lg N erişim yapar.

N = 1 milyar → en fazla 30 adım. Quick-find’da 1 milyar!

🧪 Ölçelim: dört algoritma yarışıyor

🧪 Kod laboratuvarı: ağırlıklı union

Şu anki kod doğru cevap veriyor ama ağaçlar derinleşiyor (laboratuvar uyaracak). Ağırlıklı hale getir: tüm testlerde “en derin ağaç ≤ lg N” olmalı.

LEVEL 4

Yol Sıkıştırma

path compression — her find ağacı biraz daha düzleştirsin

problem: dinamik bağlantı
quick-find
quick-union
ağırlıklandırma
yol sıkıştırma
uygulamalar
perde arkası

Fikir: kökü bulurken yolu kısalt

find(p) kökü ararken zaten yoldaki düğümlerin hepsinden geçiyor. Madem geçiyoruz, onları köke yakınlaştıralım!

Tam sıkıştırma: yoldaki her düğümü doğrudan köke bağla (iki geçiş)
Yarılama path halving: her düğümü dedesine bağla — tek satır kod!

💡 Kendini düzenleyen yapıBağlı listeler dersindeki “sık arananı öne al” fikri gibi: yapı, kullanıldıkça kendini iyileştiriyor.

Yol sıkıştırma — animasyon

Yol sıkıştırma — kod

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`id[p] = id[id[p]]`	p’yi dedesine bağla	her find yolu yarıya indirir (yarılama)
tek satır ek	ağırlıklı union’a eklenir	find çağrıldıkça ağaçlar kendiliğinden düzleşir
sonuç	pratikte sabit iş	lg* N ≤ 5: evrendeki atom sayısı kadar eleman için bile
tam sıkıştırma (alternatif)	yoldaki herkesi doğrudan köke bağla	ikinci bir geçiş gerekir; yarılama tek geçişte neredeyse aynı etkiyi verir

📐 Neredeyse sabit: lg* N ve Ackermann’ın tersi

Ağırlıklandırma + yol sıkıştırma ile M işlem, ~M · lg* N sürer.

lg* N (“log yıldız”): 1’e inene kadar kaç kez logaritma alabilirsin?

N	lg* N
2	1
16	3
65.536	4
2⁶⁵⁵³⁶ (evrendeki atomlardan çok, çok fazla)	5

📜 Bir sınırın hikâyesi 1964’te Galler ve Fischer’in ortaya attığı bu yapının tam analizi on yıl sürdü. 1975’te Robert Tarjan, maliyetin aslında daha da yavaş büyüyen ters Ackermann fonksiyonu α(N) ile sınırlı olduğunu kanıtladı. 1989’da Fredman ve Saks da bundan iyisinin imkânsız olduğunu gösterdi.

Pratikte: N ne olursa olsun işlem başına ≤ 5 adım. “Neredeyse sabit zaman.”

Dört algoritmanın karnesi 📋

algoritma	başlatma	union	find / connected	M işlem, N nesne
quick-find	N	N	1	M · N
quick-union	N	ağaç yüksekliği*	ağaç yüksekliği	M · N (en kötü)
ağırlıklı QU	N	lg N*	lg N	M · lg N
ağırlıklı QU + yol sıkıştırma	N	≈ 1*	≈ 1	≈ M (M · α(N))

* kökleri bulma maliyeti dahil. 10⁹ union ve 10⁹ find: quick-find ile 30 yıl, ağırlıklı + yol sıkıştırma ile 6 saniye. İyi algoritma, süper bilgisayardan değerlidir.

🐍 Kod laboratuvarı — Python: yol sıkıştırmalı find

Şu anki kod doğru ama sıkıştırma yapmıyor. Yarılama satırını ekle (parent[p] = parent[parent[p]]) ve “en derin ağaç” sütununun nasıl değiştiğine bak. Sonra iki geçişli tam sıkıştırmayı dene.

LEVEL 5

Uygulamalar

labirentler · perkolasyon · Go

problem: dinamik bağlantı
quick-find
quick-union
ağırlıklandırma
yol sıkıştırma
uygulamalar
perde arkası

🌀 Labirent üretimi: rastgele Kruskal

Labirent üretimi — kod

🎒 2B ızgarayı tek boyuta indirmek: hücre (x, y) → y * cols + x. Union–find nesneleri 0…N−1 diye numaralanmış ister.

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`c = y * cols + x`	iki boyutlu hücreyi tek numaraya çevir	union-find düz numaralarla çalışır
`walls.push([c, c + 1])`, `[c, c + cols]`	her hücrenin sağ ve alt duvarı	her iç duvar bir kez listelenir
`shuffle(walls)`	duvarları rastgele sıraya koy	her çalıştırmada farklı labirent
`if (!uf.connected(a, b))`	iki taraf henüz bağlı değilse duvarı yık	bağlıysa yıkmak döngü yaratırdı: tek çözümlü labirent
sonuç	tam hücre − 1 geçit	bir yayılan ağaç: her hücreye ulaşılır, iki hücre arasında tek yol (rastgele Kruskal)

💧 Perkolasyon: su öbür tarafa sızar mı?

N×N bir ızgarada her hücre p olasılıkla açık. Üstten dökülen su, açık hücrelerden geçerek alta ulaşabiliyor mu?

Gözenekli bir taştan su sızması, bir ormanda yangının yayılması, bir ağda bağlantı…
Union–find ile: açık komşuları birleştir; üst sıraya sanal bir üst düğüm, alt sıraya sanal bir alt düğüm bağla → connected(üst, alt)?

📜 Formülü yok!Büyük N için keskin bir eşik var: p < p* ise neredeyse hiç sızmaz, p > p* ise neredeyse hep sızar. Ama p* için bilinen bir formül yok; fizikçiler değeri sadece bilgisayar simülasyonuyla biliyor: ≈ 0,5927. Hızlı bir union–find olmadan bu deneyleri yapmak imkânsız.

💧 Perkolasyon deneyi

⚫ Go: taş grupları = bağlı bileşenler

Başka nerelerde?

🪄

Sihirli değnekResim düzenleyicilerde aynı renkli bitişik pikselleri seçmek (bağlı bileşen etiketleme)

🏝️

Prosedürel haritalar“Tüm odalar girişe bağlı mı?” — değilse koridor ekle

🏗️

Fizik / yıkımBir köprü parçası koparsa, hangi parçalar zemine bağlı kalır?

🌲

Kruskal MSTEn ucuz kablo/yol ağı — graflar dersinde

🔬

Fizik ve kimyaHoshen–Kopelman (1976): malzemelerdeki kümeleri saymak

🧮

DerleyicilerTür eşitleme (tip çıkarımı), denklik sınıfları

LEVEL 6

Perde Arkası

nesne yok, çöp yok: sadece tamsayı dizileri

problem: dinamik bağlantı
quick-find
quick-union
ağırlıklandırma
yol sıkıştırma
uygulamalar
perde arkası

⚙️ Neden bu kadar hızlı? Diziler!

⚙️ Bellek

Sadece iki int dizisi: id[] ve sz[] → N nesne için ~8N bayt
Düğüm nesnesi yok → çöp toplayıcıya iş yok (oyunlarda takılma yok)
Ağaçlar “işaretçi” yerine indeksle bağlı (bağlı listeler dersindeki boş liste gibi)

⚠️ Sınırları

Silme yok: bir bağlantıyı geri alamazsınız (Go demosunda baştan kurduk)
Yolu vermez: “bağlı mı?” der ama “hangi yoldan?” demez → onun için graf aramaları (DFS/BFS) gerekir
Nesneler önceden numaralanmalı (gerekirse sözlükle)

Ders: hızlı algoritma > hızlı bilgisayar. Quick-find ile 30 yıl süren iş, doğru algoritmayla 6 saniye.

Derin hikâye: Hex’te beraberlik yoktur

Hex: altıgenlerden oluşan eşkenar dörtgen bir tahta; bir oyuncu kendi iki karşı kenarını, öteki diğer iki kenarı birleştirmeye çalışır. Danimarkalı Piet Hein 1942’de, John Nash ise Princeton’da 1948’de oyunu birbirinden bağımsız olarak icat etti (Princeton’daki öğrenciler ona “Nash” derdi).
Matematiksel bir gerçek: tahta tamamen dolduğunda tam olarak bir oyuncu kazanmış olur; beraberlik imkânsızdır. David Gale 1979’da bunun Brouwer sabit nokta teoremine denk olduğunu gösterdi.
Nash, “strateji çalma” argümanıyla ilk oyuncunun kazanan bir stratejisi olduğunu ispatladı; ama bu stratejinin ne olduğunu söylemez. Büyük tahtalarda hâlâ bilinmiyor.
Program olarak: her taş konduğunda aynı renkli komşularıyla birleştir; iki kenarı temsil eden iki sanal düğüm aynı kümede mi, diye bul. Her hamle neredeyse sabit sürede kontrol edilir.

DersUnion-Find, “bu iki şey bağlı mı?” sorusunu sadece birleşmeler olurken çok hızlı cevaplar: Hex, Go’daki taş grupları, eşleştir-3 oyunlarındaki gruplar, Kruskal. Sanal düğüm (kenarlar için) hilesi birçok bağlantı probleminde işe yarar.

Kaynak: Wikipedia: Hex · Gale 1979

🧰 Kütüphaneler ve araçlar

ad	platform	ne yapar / sınırları	nasıl eklenir
scipy DisjointSet	Python (SciPy 1.6+)	merge, connected, subset; hazır ayrık küme.	`pip install scipy`
networkx.utils.UnionFind	Python	Basit union-find yardımcı sınıfı.	`pip install networkx`
scipy.ndimage.label	Python	Izgarada bağlı bileşen etiketleme (görüntü, harita).	`pip install scipy`
boost::disjoint_sets	C++	Rank ve yol sıkıştırmalı ayrık kümeler.	Boost
kendi sınıfınız	C# / Unity	.NET’te hazır yok; 30 satırlık bir sınıf (int[] parent, int[] size) yeterli ve çöp üretmez.	—

🧩 Oyunlarda Union-Find

Kazanma kontrolü: Hex, bağlantı bulmacaları (borular/kablolar birleşti mi?).
Gruplar: Go’da taş grupları, eşleştir-3’te aynı renkli kümeler, kalabalıkta bölüklere ayrılma.
Prosedürel üretim: Kruskal ile labirent ve zindan koridorları (MST sunumu).
Sızma (percolation): ateşin ya da suyun yayılıp karşı kenara ulaşıp ulaşmadığı.

Bilmeniz gereken sınırUnion-Find silmeyi desteklemez: bir duvar yıkılınca birleşir, ama yeniden örülünce ayıramazsınız. Bağlantı kopabiliyorsa (yıkılan köprü) ya baştan kurun ya da BFS kullanın. Ayrıca yol sıkıştırma ve boyuta göre birleştirme olmadan en kötü durum O(n)’dir.

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

Yol sıkıştırmayı unutmak
Boyuta/rank’a göre birleştirmeyi unutmak
Silme desteklediğini sanmak
Özyinelemeli find ile derin ağaçta yığın taşması

İyi bir istek (prompt) örneği

“Unity 6, C#. Hex oyunu yaz: 11×11 altıgen ızgara (eksenel koordinatlar), iki oyuncu sırayla taş koyar. UnionFind sınıfı (int[] parent, int[] size, yol sıkıştırmalı ve özyinelemesiz Find, boyuta göre Union); her oyuncu için iki sanal kenar düğümü; her hamleden sonra kazanma kontrolü. Altıgen komşuluklarını ve kazanma kontrolünü test eden NUnit testleri ekle.”

Yol sıkıştırma + boyuta göre birleştirmeyi açıkça isteyin
Özyinelemesiz find isteyin
Silme gerekiyorsa bunu söyleyin (yanlış yapı!)
Sanal düğüm hilesini sorun

🚀 Proje ve araştırma önerileri

[kolay] Hex — Yukarıdaki istemdeki oyun; iki kişilik yerel oyun.
[orta] Eşleştir-3 grupları — Her hamleden sonra aynı renkli grupları Union-Find ile bulup patlatın.
[orta] Kruskal labirenti — Rastgele sıralı duvarları Union-Find ile kaldırarak mükemmel labirent üretin.
[araştırma] Silme ile bağlantılılık — Çevrimdışı (tüm işlemler önceden bilinen) dinamik bağlantılılık yöntemlerini araştırıp küçük bir örnek yazın.

📄 Akademik okumalar ve kaynaklar

Galler & Fischer 1964 · An Improved Equivalence Algorithm (Communications of the ACM 7(5))
Ayrık küme ormanının ilk tanımı.

Tarjan 1975 · Efficiency of a Good But Not Linear Set Union Algorithm (Journal of the ACM 22(2))
Ters Ackermann sınırı.

Gale 1979 · The Game of Hex and the Brouwer Fixed-Point Theorem (American Mathematical Monthly 86(10))
Hex’te beraberlik olmamasının ispatı.

Neler öğrendik? 🎒

Dinamik bağlantı: union, find, connected, bileşenler.
Quick-find: soru 1, birleştirme N → karesel.
Quick-union: ağaçlar; dikkat edilmezse zincir olur.
Ağırlıklı: küçük ağaç büyüğün altına → derinlik ≤ lg N.

Yol sıkıştırma: neredeyse sabit (α(N) ≤ 5).
🎮 Kruskal ile labirentler, Go grupları, yıkım fiziği.
🔬 Perkolasyon: simülasyonla keşfedilen sabit.
⚙️ Sadece tamsayı dizileri; sınırlar: silme yok, yol yok.

Alıştırmalar 🏋️

Kâğıt-kalem: 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 bağlantıları için quick-find’ın id[] dizisini her adımda yazın. Sonra aynısını ağırlıklı quick-union için yapıp ormanı çizin.
Union–find sınıfına bir bileşenin en büyük elemanını döndüren findMax(p) ekleyin (ipucu: köklerde bir dizi daha tutun).
p5.js’te labirent üreticisini yazın; sonra labirentin girişinden çıkışına giden yolu bulmak için ne gerekir? (İpucu: yığınlar dersindeki DFS!)
Unity’de 10×10 bloktan bir duvar yapın; tıklanan blok yok olsun ve zemine bağlı olmayan bloklar düşsün (her tıklamada union–find’ı baştan kurun).
Perkolasyon demosunda N’i 10 ve 30 yaparak Monte Carlo deneyleri yapın: eşik değeri N’e bağlı mı?
🤖 Bir YZ asistanından “C#’ta union-find” isteyin. Ağırlıklandırma ve yol sıkıştırma var mı? Yoksa ekletin ve farkı ölçün.