Minimum Yayılan Ağaçlar

OYUNLARDA YAPAY ZEKÂ · GRAFLAR

Kruskal, Prim ve kesme özelliği — her şeyi en ucuza bağlamak

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

Tanım — ağırlıklı graf, yayılan ağaç spanning tree
Kesme özelliği — bütün MST algoritmalarının sırrı cut property
Kruskal — en ucuz kenardan başla, döngü yapma (Union–Find!)
Prim — bir düğümden büyüt (öncelik kuyruğu!)
Oyunda MST — prosedürel zindan koridorları, labirentler, birlik kümeleme
Bağlam — 1926’dan bugüne, hâlâ çözülmemiş soru

🎮 Bu dersin sonunda…

…rastgele yerleştirilmiş odaları en az koridorla birbirine bağlayan bir zindan üreticisi yazabilecek ve bunun için daha önce öğrendiğiniz iki veri yapısını (Union–Find ve öncelik kuyruğu) birlikte kullanacaksınız.

🤔 ISINMA: ADALARI BAĞLA

Bir strateji oyununda 8 ada var. Aralarına köprü kurmak pahalı: her köprünün maliyeti farklı. Bütün adalar birbirine (dolaylı da olsa) bağlı olmalı.

En az kaç köprü gerekir? → 7 (ada sayısı − 1). Daha fazlası gereksiz bir döngü kurar.
Hangi 7 köprü, toplam maliyet en az olacak şekilde?
Olası köprü setleri: milyarlarca! Hepsini denemek imkânsız.

Şaşırtıcı haber: açgözlü greedy davranmak (hep en ucuz köprüyü seçmek, döngü yapmadıkça) kesinlikle en iyi sonucu verir.

Mini sözlük

edge-weighted graph	kenar ağırlıklı graf	Her kenarın bir maliyeti (uzunluk, para, süre) var
spanning tree	yayılan ağaç	Bütün düğümleri kapsayan, döngüsüz, bağlı alt graf (V − 1 kenar)
MST	minimum yayılan ağaç	Ağırlıkları toplamı en küçük yayılan ağaç
cut · crossing edge	kesme · kesişen kenar	Düğümleri iki gruba ayırma · iki grubu birleştiren kenar
greedy algorithm	açgözlü algoritma	Her adımda o an en iyi görüneni seçen, geri dönmeyen algoritma
lazy / eager Prim	tembel / hevesli Prim	Bayat kenarları PQ’da bırakan / hemen güncelleyen sürüm

LEVEL 0

Tanım

ağırlıklı graf ve yayılan ağaç

tanım
kesme özelliği
Kruskal
Prim
oyunda MST
bağlam

Ağırlıklı graf: örnek grafımız

8 düğüm, 16 kenar; her kenarın üstünde ağırlığı. Komşuluk listesinde artık her kayıt (komşu, ağırlık) çifti. Bir düğüme tıklayın.

Yayılan ağaç ve MST

Yayılan ağaç: grafın bir alt grafı ki

bütün düğümleri içerir,
bağlıdır (her düğümden her düğüme yol var),
döngüsüzdür (ağaç).

Sonuç: tam V − 1 kenarı vardır.

MST: toplam ağırlığı en küçük yayılan ağaç. tinyEWG için toplam 1,81.

Kolaylık varsayımları

Graf bağlı (değilse her bileşen için bir MST: “minimum yayılan orman”)
Ağırlıklar farklı (o zaman MST tektir)

Ağırlıklar negatif olabilir; algoritmalar yine çalışır (en kısa yollardan farkı!).

Saf yaklaşım: bütün ağaçları dene ya da “en kısaları al”

Altı oda (A–F), dokuz aday koridor; sayılar koridor uzunluğu. Renkli kenarlar: “en kısa 5 koridoru al” denemesi.

Saf yol 1: bütün yayılan ağaçları say, en ucuzunu seç

Bu küçük grafta 55 farklı yayılan ağaç var; elle bile yorucu.
Her odadan her odaya koridor açılabiliyorsa n oda için nⁿ⁻² ağaç var (Cayley formülü): 6 oda → 1 296; 20 oda → 20¹⁸ ≈ 2,6 × 10²³.

Saf yol 2: “en kısa V − 1 kenarı al” Hızlı ama yanlış: B–C 1, B–D 2, A–C 3, E–F 3, A–B 4. Beş kenar aldık ama A–B–C döngü oldu (A–B boşa kazıldı), E ve F öbür odalara bağlanmadı.

Doğru fikirAçgözlülük doğru yolda; eksik olan tek şey bir kontrol: “bu koridor zaten bağlı iki odayı mı birleştiriyor?” O kontrolü ekleyince Kruskal çıkar; maliyet E log E.

MST nerede kullanılır?

alan	düğüm	kenar ağırlığı
Ağ tasarımı (elektrik, telefon, internet kablosu)	şehir / bina	kablo maliyeti
🎮 Prosedürel zindan / harita	oda / ada / şehir	koridor / yol uzunluğu
🎮 Labirent üretimi	hücre	rastgele
🎮 Birlikleri gruplara ayırma (kümeleme)	birim	mesafe
Görüntü bölütleme, kanser araştırması	piksel / hücre	benzemezlik
Gezgin satıcı için yaklaşık çözüm	şehir	mesafe

🔗 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.

📊 En küçük kapsayan ağaç

VisuAlgo (NUS)

Kruskal ve Prim’i aynı graf üzerinde, kenar kenar karşılaştırın.

🔗 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 · tanım

50 odalı bir zindanın odalarını koridorlarla bağlayan bir yayılan ağaçta kaç koridor vardır?

Her yayılan ağacın tam V − 1 kenarı vardır: 50 oda → 49 koridor. Bir eksik olsa graf bağlı olmaz; bir fazla olsa döngü oluşur. Hangi 49 koridor olacağı ise ağırlıklara bağlı — MST onu seçer.

LEVEL 1

Kesme özelliği

cut property — açgözlülük neden doğru?

tanım
kesme özelliği
Kruskal
Prim
oyunda MST
bağlam

Kesme özelliği — kendiniz deneyin

Hangi kesmeyi seçerseniz seçin, yeşil kenar (en hafif kesişen) her zaman bu grafın MST’sindeki 7 kenardan biri: 0–7, 1–7, 0–2, 2–3, 5–7, 4–5, 6–2.

Kesme özelliği ve kanıtı

Önerme (kesme özelliği)Herhangi bir kesmede, en hafif kesişen kenar MST’dedir.

Kanıt (değiş-tokuş)

Diyelim ki en hafif kesişen kenar e, MST’de yok.
e’yi MST’ye ekle → bir döngü oluşur.
Bu döngü kesmeyi bir kez e ile geçiyor; geri dönmek için kesmeyi başka bir kenarla (f) da geçmeli.
f’yi çıkar: hâlâ yayılan ağaç, ama e, f’den hafif → toplam ağırlık azaldı. MST daha hafif olamaz → çelişki! ∎

Genel açgözlü algoritma

Bütün kenarlar başta gri
Siyah kenarlardan hiçbirinin geçmediği bir kesme bul
O kesmenin en hafif kesişen kenarını siyaha boya (MST’ye al)
V − 1 kenar siyah olana kadar tekrarla

İki ünlü seçimKesmeyi nasıl seçtiğiniz algoritmayı belirler:

Kruskal: kenarları hafiften ağıra dene
Prim: kesme = “şimdiye kadarki ağaç” vs “geri kalan”

Quiz 2 · kesme özelliği

Bir düğümün en hafif kenarı hakkında ne söylenebilir? (Ağırlıklar farklı.)

Kesme = {o düğüm} ve {geri kalan herkes}. Bu kesmenin kesişen kenarları tam o düğümün kenarları. En hafifi → kesme özelliğiyle MST’de. (Borůvka algoritması tam bu fikirle başlar!)

LEVEL 2

Kruskal

kenarları ucuzdan pahalıya dene, döngü yapanı at

tanım
kesme özelliği
Kruskal
Prim
oyunda MST
bağlam

Kruskal algoritması

Renkler = şimdiki bileşenler (orman). Bir kenar iki farklı renkteki düğümü bağlıyorsa alınır ve iki renk birleşir; aynı renkse döngü yapacağı için atılır. “Aynı bileşende mi?” sorusu… Union–Find (Ders 1)!

Elle izleme: Kruskal, altı odada

Alınma sırası tabloda. Yeşil = MST’ye girdi, kırmızı kesikli = döngü yapacağı için atlandı. C–E (6) ve D–F (7) hiç denenmedi: ağaç 7. adımda tamamlandı.

Kenarları hafiften ağıra diz: B–C 1, B–D 2, A–C 3, E–F 3, A–B 4, C–D 4, D–E 5, C–E 6, D–F 7.

#	kenar	ağırlık	gruplar (önce)	karar
1	B–C	1	{A} {B} {C} {D} {E} {F}	al
2	B–D	2	{A} {B, C} {D} {E} {F}	al
3	A–C	3	{A} {B, C, D} {E} {F}	al
4	E–F	3	{A, B, C, D} {E} {F}	al
5	A–B	4	{A, B, C, D} {E, F}	atla: A ile B aynı grupta (A–C–B)
6	C–D	4	{A, B, C, D} {E, F}	atla: C–B–D zaten var
7	D–E	5	{A, B, C, D} {E, F}	al → 5 kenar = V − 1, dur

MST: B–C, B–D, A–C, E–F, D–E · toplam 1 + 2 + 3 + 3 + 5 = 14.

“Gruplar” sütunu Union–Find’ın tuttuğu şey: connected(A, B) 5. adımda true döner, kenar atlanır. Eşit ağırlıklar (A–C ile E–F) hangi sırayla gelirse gelsin toplam değişmez.

Kruskal — kod

🎒 Kruskal kodundaki yeni ifadeler: sıralama anahtarı

sorted(edges, key=lambda e: e[2])	Python	“Kenarları 3. elemanlarına (ağırlığa) göre sırala.” `lambda e: e[2]` = “e alır, e[2] döndürür” kısa fonksiyonu
(a, b) => a.wt.CompareTo(b.wt)	C#	İki kenarı karşılaştıran fonksiyon: negatif → a önce, pozitif → b önce
(a, b) => a[2] - b[2]	JavaScript	Aynı fikir: fark negatifse a önce
(int v, int w, double wt)	C# demet	Sınıf yazmadan üç alanlı küçük kayıt

Lambda yerine geleneksel yol (Python): ayrı bir fonksiyon yazıp adını vermek:

Kruskal: doğru mu, ne kadar sürer?

ÖnermeKruskal algoritması MST’yi bulur. Süresi en kötü durumda E log E ile orantılıdır.

Neden?

Doğruluk: alınan kenar v–w’de, kesme = {v’nin bileşeni} vs {geri kalan}. Daha hafif kesişen kenar olsaydı daha önce denenmiş ve alınmış olurdu → e en hafif kesişen kenar → kesme özelliği ✔
Süre: sıralama E log E + E kez Union–Find (≈ sabit) → E log E

Bir başka sürüm sıralamak yerine bir öncelik kuyruğu (MinPQ) kullanır: aynı süre, ama erken bitince geri kalan kenarları hiç sıralamamış olur.

🧪 Kod laboratuvarı: Kruskal

Bu kod her zaman bir yayılan ağaç buluyor — ama minimum değil! Hangi satır eksik? (İpucu: Kruskal kenarlara hangi sırayla bakmalı?) Bonus: uf.union’un true/false dönüşünü kullanarak if’i tek satıra indirin.

LEVEL 3

Prim

tek bir düğümden başla, ağacı büyüt

tanım
kesme özelliği
Kruskal
Prim
oyunda MST
bağlam

Prim algoritması (tembel sürüm)

Mavi = ağaçtaki düğümler. Kesme = “ağaç” vs “ağaç dışı”. Ağacın dışarı uzanan kenarları bir öncelik kuyruğunda (Öncelik Kuyrukları sunumu!); her adımda en hafifi alınır. İki ucu da ağaca girmiş kenarlar “bayat” olur: çıkınca atılır (tembellik).

Elle izleme: Prim (tembel), A odasından

Rozet = odanın ağaca giriş adımı. Mavi = ağaç kenarı; kırmızı kesikli = PQ’dan bayat çıkıp atılan; gri kesikli = ağaç bitince PQ’da kalan.

#	PQ’dan çıkan (en hafif)	karar	PQ’ya eklenen
0	—	A ağaçta	A–C 3, A–B 4
1	A–C 3	C ağaca	C–B 1, C–D 4, C–E 6
2	C–B 1	B ağaca	B–D 2
3	B–D 2	D ağaca	D–E 5, D–F 7
4	A–B 4	bayat: A da B de ağaçta, at	—
5	C–D 4	bayat, at	—
6	D–E 5	E ağaca	E–F 3
7	E–F 3	F ağaca → 6 oda, dur	—

Ağaç: A–C, C–B, B–D, D–E, E–F · toplam 3 + 1 + 2 + 5 + 3 = 14. Kruskal’la aynı beş kenar, başka sırayla.

Yalnızca ucu ağaç dışında olan kenarlar PQ’ya eklenir (C eklenirken C–A eklenmez). A–B eklendiği anda iyi bir adaydı; B, C üzerinden ucuza bağlanınca bayatladı. “Tembel” sürüm onu hemen silmez, çıkınca atar.

Prim — kod (tembel, MinPQ ile)

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`visit(v)`	v’yi ağaca al, kesişen kenarlarını kuyruğa ekle	ağaçtan dışarı çıkan her kenar aday
`pq.pop()`	en hafif aday kenar	kesme özelliği: ağaç ile geri kalan arasındaki en hafif kenar MST’dedir
`if (marked[v] && marked[w]) continue`	iki ucu da ağaçta: bayat kenar	sonradan iki ucu da eklenmiş kenar artık kesmeyi geçmiyor; atla (tembel Prim)
`visit(marked[w] ? v : w)`	ağaçta olmayan ucu ekle	kenarın hangi ucunun yeni olduğunu bilmiyoruz
maliyet	~E log E	her kenar kuyruğa en çok bir kez girer ve çıkar

Prim mi, Kruskal mı?

algoritma	fikir	yardımcı yapı	süre
Kruskal	ormanları birleştir	sıralama + Union–Find	E log E
Prim (tembel)	tek ağacı büyüt	MinPQ (kenarlar)	E log E
Prim (hevesli)	tek ağacı büyüt	indeksli MinPQ (düğümler)	E log V

PratikteSeyrek graflarda (oyun haritaları) ikisi de çok hızlı. Kenarlar zaten bir listede ise Kruskal yazması daha kolay; graf büyük ve komşuluk listesiyle tutuluyorsa Prim.

⚙️ Hevesli PrimPQ’da kenar değil düğüm tutulur: “bu düğümü ağaca bağlamanın şimdiki en ucuz yolu”. Daha ucuz yol bulununca öncelik düşürülür (decreaseKey). PQ en fazla V elemanlı → E log V. Aynı fikri Dijkstra’da göreceğiz!

🎬 Ara: Kruskal, 2 dakikada

Kruskal’s algorithm in 2 minutes
Michael Sambol · 1 dk 49 sn · YouTube’da aç

Kenarları kısadan uzuna sırala, döngü yapmayanı al: Kruskal’ın en kısa görsel özeti. Hemen ardından aynı kanalın Prim videosu (Kaynaklar) iki yöntemi karşılaştırmak için iyi.

🤔 İzlerkenVideoda atlanan kenar neden atlanıyor? “Döngü yapar mı?” sorusunu hızlı cevaplamak için hangi veri yapısını kullanırız?

Quiz 3 · Prim

Tembel Prim’de PQ’dan çıkan bir kenarın iki ucu da ağaçtaysa neden atılır?

Kenar PQ’ya girdiğinde bir ucu ağaçta, öteki dışarıdaydı (kesişen kenar). Sonra öteki uç başka bir kenarla ağaca katıldı → kenar “bayat”. Eklemek döngü yaratır. Tembel sürüm bu kenarları baştan silmek yerine çıkınca atlar.

🐍 Kod laboratuvarı — Prim (Python)

Toplam fazla çıkıyor. Neden? (İpucu: PQ’dan çıkan her kenar gerçekten ağaca mı ekleniyor? Bayat kenarlar ne olacak?) Düzeltin.

LEVEL 4

Oyunda MST

zindan koridorları, labirentler, birlik grupları

tanım
kesme özelliği
Kruskal
Prim
oyunda MST
bağlam

Problem: rastgele odaları koridorlarla bağlamak

🎮 Zindan üreticisinin derdi

Her oyunda farklı bir zindan istiyoruz (Y15). Odaları rastgele serpmek kolay; zor olan onları koridorlarla bağlamak:

Her odaya ulaşılabilmeli (giriş odasından patron odasına yol olmalı).
Gereksiz koridor olmamalı: her koridor kazı, ışık, düşman demek.
Koridorlar kısa olmalı: haritanın bir ucundan öbür ucuna giden tüneller çirkin durur.

Graf olarak: odalar düğüm, olası koridorlar kenar, kenarın ağırlığı koridorun uzunluğu.
İstenen: bütün odaları bağlayan, toplam uzunluğu en küçük koridor kümesi = en küçük kapsayan ağaç (MST).
Kruskal bunu şöyle bulur: adayları kısadan uzuna sırala; sıradaki koridor henüz bağlı olmayan iki odayı birleştiriyorsa kaz, yoksa atla.

Elle izleme: dört oda, beş aday koridor

sıra	aday	uzunluk	gruplar (önce)	karar
1	A–B	3	{A} {B} {C} {D}	kaz
2	C–D	4	{A, B} {C} {D}	kaz
3	A–C	5	{A, B} {C, D}	kaz (iki grubu birleştirir)
4	B–C	6	{A, B, C, D}	atla: ikisi zaten bağlı
5	B–D	9	{A, B, C, D}	atla

Sonuç: 4 oda, 3 koridor (her zaman oda sayısı − 1), toplam 3 + 4 + 5 = 12 birim. B–C’yi de kazsaydık A → B → C → A diye bir döngü oluşurdu: fazladan 6 birim kazı, yeni hiçbir odaya ulaşmadan.

Odalara harf veriyoruz ki uzunluklarla (sayılar) karışmasın. “Gruplar” sütununu tutan veri yapısı Union-Find sunumundaki birleşim-bulma: demoda her grup ayrı bir renk.

🧭 DEMOYU OKUMA KILAVUZU (bir sonraki slayt)

Dikdörtgenler odalar (A = giriş, son harf = patron odası). İnce gri çizgiler aday koridorlar; kazılmış koridorlar kalın kahverengi.
Odanın rengi, bağlı olduğu grubu gösterir. Başta her oda ayrı renktedir. Bir koridor kazılınca iki grup aynı renge boyanır. Bütün odalar tek renk olduğunda zindan bağlanmıştır.
“İleri ▶|” ile adım adım gidin. Sarı çizgi şu an bakılan aday; üstündeki sayı uzunluğu. İki ucu farklı renkteyse kazılır; aynı renkteyse kırmızı kesikli olur ve atlanır.
Sayaçlardan “ayrı grup”u izleyin: her kazıda bir azalır; 1 olunca ağaç tamamdır.
Son adım tasarım kararı: ağaçta her iki oda arasında tek yol vardır. Atlanan koridorların bir kısmı geri eklenir (mor): oyuncu dolanabilsin, düşmandan kaçabilsin.

🎮 Prosedürel zindan: odaları MST ile bağla

Dikdörtgenler odalar (A = giriş, son harf = patron odası). İnce gri çizgiler aday koridorlar; kazılmış koridorlar kalın kahverengi.
Odanın rengi, bağlı olduğu grubu gösterir. Başta her oda ayrı renktedir. Bir koridor kazılınca iki grup aynı renge boyanır. Bütün odalar tek renk olduğunda zindan bağlanmıştır.
“İleri ▶|” ile adım adım gidin. Sarı çizgi şu an bakılan aday; üstündeki sayı uzunluğu. İki ucu farklı renkteyse kazılır; aynı renkteyse kırmızı kesikli olur ve atlanır.
Sayaçlardan “ayrı grup”u izleyin: her kazıda bir azalır; 1 olunca ağaç tamamdır.
Son adım tasarım kararı: ağaçta her iki oda arasında tek yol vardır. Atlanan koridorların bir kısmı geri eklenir (mor): oyuncu dolanabilsin, düşmandan kaçabilsin.

🔗 Ayrıntısı: G10 · Üçgenleme ve Voronoi (Delaunay + MST ile beş aşamalı zindan) · Y15 · Prosedürel Üretim sunumunda.

TinyKeep tarifi (adım adım)

Rastgele boyutlu odalar üret, çakışanları it/ayır
Büyük odaları “ana oda” seç
Oda merkezleri arasında aday kenarlar: Delaunay üçgenlemesi (biz basitçe “en yakın 4 komşu” kullandık)
MST → her oda ulaşılabilir, koridor sayısı en az
MST dışından birkaç kenarı (~%10–15) geri ekle → döngüler, kestirme yollar
Kenarları L biçimli koridorlara çevir; koridorun geçtiği küçük odaları da zindana kat

Neden MST + biraz fazlası?Saf MST bir ağaç: her iki oda arasında tek yol → bol çıkmaz, sürekli geri dönüş. Saf tam graf: her yerden her yere koridor → labirent hissi yok. Seviye tasarımı ikisi arasında bir denge.

Kaynak: A. Adonaac, “Procedural Dungeon Generation Algorithm” (Game Developer), TinyKeep oyunundan esinlenerek.

Labirentler ve kümeleme

🌀 Labirent = rastgele ağırlıklı ızgaranın MST’siIzgaradaki her duvara rastgele bir ağırlık ver; MST’yi (Kruskal) bul; MST kenarlarının duvarlarını yık. Sonuç: her hücreye tek yol olan “mükemmel labirent”. (Union–Find sunumundaki labirent tam buydu!) Prim ile üretilen labirentler daha kısa, dallı koridorlu olur — tadı farklı.

⚔️ Birlikleri k gruba ayırBirim konumlarının MST’sini bul, en ağır k − 1 kenarı sil → k bağlı bileşen = k küme (tek bağlantılı kümeleme). RTS’de seçili 40 birimi otomatik takımlara bölmek ya da ekranda “ordu” etiketlerini gruplamak için.

Quiz 4 · oyunda

Zindan üreticisi saf MST koridorlarını kullansaydı oyuncu deneyimi nasıl olurdu?

MST bir yayılan ağaç: bağlı (herkes ulaşılabilir) ama döngüsüz (alternatif rota yok). Bu yüzden tasarımcılar MST dışından birkaç kenarı geri ekleyip döngüler oluşturur — oyuncuya seçenek ve kestirme verir.

LEVEL 5

Bağlam

bir asırlık bir problem ve hâlâ açık bir soru

tanım
kesme özelliği
Kruskal
Prim
oyunda MST
bağlam

📜 MST’nin tarihi

yıl	kim	ne
1926	Otakar Borůvka	Moravya’nın (Çekya) elektrik şebekesini en ucuza kurmak için — ilk MST algoritması
1930	Vojtěch Jarník	Bugün “Prim” dediğimiz algoritma (Çek dergisinde, fark edilmedi)
1956	Joseph Kruskal	Kruskal algoritması (bir sayfalık makale)
1957 · 1959	Robert Prim · Edsger Dijkstra	Jarník’in algoritmasını bağımsız olarak yeniden buldular
2000	Bernard Chazelle	Neredeyse doğrusal: E α(V) (α = Union–Find’daki ters Ackermann!)
???	siz?	Doğrusal zamanlı (E) deterministik bir MST algoritması var mı? Hâlâ bilinmiyor!

Quiz 5 · bağlam

Kruskal algoritmasının çalışma süresinde baskın olan (en pahalı) adım hangisidir?

Union–Find işlemleri (yol sıkıştırmalı, ağırlıklı) neredeyse sabit; E tanesi ~E. Sıralama ise E log E. Kenarlar zaten sıralı gelirse (ya da ağırlıklar küçük tam sayılarsa ve sayma sıralaması kullanılabilirse) Kruskal neredeyse doğrusal çalışır.

Derin hikâye: TinyKeep’in zindanları: odalar + Delaunay + MST

Bağımsız geliştirici Phi Dinh, oyunu TinyKeep için 2013’te paylaştığı zindan üretme yöntemini anlattı; yöntem bugün hâlâ çok kopyalanır:
1) Bir alana rastgele boyutlu çok sayıda oda yerleştir, çakışanları birbirinden it (Y7’deki ayrılma kuvveti gibi). 2) Büyük odaları “ana oda” seç. 3) Ana odaların merkezlerinden Delaunay üçgenlemesi yap (bütün yakın komşuluklar). 4) Bu graftan minimum yayılan ağaç çıkar: her oda bağlı, gereksiz koridor yok. 5) Ağaca, silinen kenarlardan rastgele birkaç tanesini geri ekle: tamamen ağaç bir zindan çıkmaz sokaklarla dolu olur, birkaç döngü keşfi eğlenceli yapar. 6) Kenarları L biçimli koridorlara çevir.

DersMST burada “en ucuz bağlantı” değil, “herkes bağlı, hiçbir şey fazla değil” iskeleti olarak kullanılıyor; tasarım için bilerek bozuluyor (geri eklenen kenarlar). Algoritmalar çoğu zaman bir tasarım aracının parçasıdır, son ürünün kendisi değil (Y15’teki “önce yapı, sonra ayrıntı”).

Kaynak: Game Developer: Procedural Dungeon Generation Algorithm

🧰 Kütüphaneler ve araçlar

ad	platform	ne yapar / sınırları	nasıl eklenir
networkx.minimum_spanning_tree	Python	Kruskal, Prim ve Borůvka seçenekleriyle MST.	`pip install networkx`
scipy.sparse.csgraph.minimum_spanning_tree	Python	Seyrek matris üzerinde hızlı MST.	`pip install scipy`
scipy.spatial.Delaunay	Python	Noktalardan Delaunay üçgenlemesi (zindan yönteminin 3. adımı).	`pip install scipy`
QuikGraph	C#	Kruskal ve Prim MST.	NuGet: `QuikGraph`
Delaunator	JavaScript (C# portu var)	Çok hızlı 2B Delaunay üçgenlemesi.	`npm install delaunator`

🧩 Oyunlarda MST

Prosedürel zindan/yol ağları: odaları/şehirleri en az koridorla bağlamak, sonra birkaç döngü eklemek.
Şehir kurma oyunları: elektrik hatları, boru ağları için en ucuz bağlantı önerisi (Borůvka’nın 1926’daki problemi!).
Kümeleme: MST’nin en uzun kenarlarını silmek noktaları gruplara ayırır (tek bağlantılı kümeleme): düşman gruplarını ya da kaynak kümelerini bulmak.
Gezgin satıcıya yaklaşım: MST’yi dolaşmak, bütün noktaları gezen turun en fazla iki katı uzunlukta bir tur verir (metrik uzaylarda); NPC’nin bütün noktaları dolaşması için yeterince iyi.

Sık hatalar

Kruskal’da kenarları sıralamayı unutmak.
Döngü kontrolünü Union-Find yerine BFS ile her kenarda yapmak (yavaş).
Yönlü grafta MST beklemek.
Eşit ağırlıklarda belirli bir ağaç çıkacağını varsaymak (tohumlu sıralama kullanın).

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

Kenarları sıralamayı unutmak
Union-Find olmadan döngü kontrolü
Yönlü grafta MST
Eşitliklerde rastgele, tekrarlanamaz sonuç

İyi bir istek (prompt) örneği

“Unity 6, C#. TinyKeep tarzı zindan üreteci yaz: (1) tohumlu System.Random ile N oda, (2) ayrılma ile çakışmaları çöz, (3) ana odaların merkezleri için Delaunay üçgenlemesi (Bowyer–Watson), (4) Kruskal + Union-Find ile MST, (5) silinen kenarların %12’sini geri ekle, (6) L biçimli koridorlar, (7) Tilemap’e çiz; Gizmos ile grafı göster. Aynı tohumun aynı zindanı ürettiğini test et.”

Hangi algoritmayı neden seçtiğini sorun
Union-Find’ı yol sıkıştırmalı isteyin
Tohumlu, tekrarlanabilir üretim isteyin
Geri eklenen kenar oranını parametre yapın

🚀 Proje ve araştırma önerileri

[kolay] MST ile ağ — p5.js’te tıklanan noktaları Prim ile bağlayan “elektrik hattı” aracı.
[orta] TinyKeep zindanı — Yukarıdaki istemdeki üreteç; döngü oranının oynanışa etkisini deneyin.
[orta] Kümeleme — Kaynak noktalarını MST’nin en uzun kenarlarını silerek gruplayın.
[araştırma] Tur yaklaşımı — MST tabanlı 2-yaklaşık turu, en yakın komşu turu ve 2-opt iyileştirmesiyle karşılaştırın.

📄 Akademik okumalar ve kaynaklar

Kruskal 1956 · On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem (Proceedings of the AMS 7(1))
Kruskal algoritması.

Prim 1957 · Shortest Connection Networks and Some Generalizations (Bell System Technical Journal 36(6))
Prim algoritması.

Nešetřil, Milková & Nešetřilová 2001 · Otakar Borůvka on Minimum Spanning Tree Problem: Translation of Both the 1926 Papers (Discrete Mathematics 233)
Borůvka’nın makalelerinin İngilizce çevirisi.

Neler öğrendik? 🎒

MST: bütün düğümleri en az toplam ağırlıkla bağlayan ağaç (V − 1 kenar).
Kesme özelliği: her kesmenin en hafif kesişen kenarı MST’de → açgözlülük doğru.
Kruskal: sırala + Union–Find; E log E.
Prim: ağacı büyüt + öncelik kuyruğu; E log E (tembel) / E log V (hevesli).

🎮 Zindan koridorları: MST + birkaç ek kenar.
🎮 Labirent: rastgele ağırlıklı ızgaranın MST’si.
🎮 Kümeleme: en ağır k − 1 kenarı sil.
Daha önce öğrendiğimiz iki yapı (UF, PQ) burada birleşti.

Alıştırmalar 🏋️

Kâğıt-kalem: tinyEWG’de Kruskal ve Prim’i (0’dan) uygulayın; kenarların eklenme sıralarını karşılaştırın.
Bir kenarın ağırlığı biraz artarsa MST nasıl değişir? MST’de olan ve olmayan kenar için ayrı düşünün.
p5.js’te: fareyle tıklanan noktaların MST’sini her tıklamada yeniden çizin (tam graf, ağırlık = mesafe).
Zindan demosundaki koridorları gerçek bir karo haritasına (0/1 ızgara) dönüştürün ve Yönsüz Graflar sunumundaki BFS ile girişten boss’a uzaklığı hesaplayın.
“Maksimum yayılan ağaç” nasıl bulunur? (İpucu: ağırlıkları eksi yapın.) Oyunda nerede işe yarar?
🤖 Bir YZ asistanından “Godot/Unity’de Delaunay + MST zindan üreticisi” isteyin. MST kısmını hangi algoritmayla yazdı? Union–Find’da yol sıkıştırma var mı?

Kaynaklar: videolar 🎬

Kruskal’s algorithm in 2 minutes
Michael Sambol

Prim’s algorithm in 2 minutes
Michael Sambol

Union Find Kruskal’s Algorithm
WilliamFiset

Prim’s Algorithm Visually Explained
ByteQuest

Connecting Rooms (Delaunay & MST) — Procedural Dungeons
DeveloperEzra

Kaynaklar: okuma 📚

FINAL LEVEL ▶

En Kısa Yollar

Dijkstra, DAG’ler, Bellman–Ford — ve oyun yapay zekâsındaki yol bulmanın kapısı

SONRAKİ SUNUM ▶