Yönsüz Graflar

OYUNLARDA YAPAY ZEKÂ · GRAFLAR

Yönsüz Graflar

Düğümler, kenarlar, DFS, BFS — oyun dünyasının iskeleti

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

Terimler — düğüm, kenar, yol, döngü, bağlılık vertex, edge, path
Gösterimler — komşuluk listesi mi, matris mi?
DFS — derinlik öncelikli arama: labirentte ip çözmek
BFS — genişlik öncelikli arama: en az adımlı yol
Bağlı bileşenler — kaç ada var? ulaşılamayan hazine var mı?
Oyunda graflar ve “kolay mı, zor mu, imkânsız mı?” listesi

🎮 Bu dersin sonunda…

…bir oyun haritasını graf olarak görecek, “oyuncu buradan oraya gidebilir mi?” ve “en az kaç adımda?” sorularını yanıtlayan kodu yazabilecek ve oyun yapay zekâsındaki yol bulmanın (A*) temelini atmış olacaksınız.

🤔 ISINMA: ZİNDAN

Bir zindanda 40 oda ve odaları bağlayan kapılar var. Oyuncu girişte, boss en dipteki odada.

Oyuncu boss’a ulaşabilir mi? (Seviye tasarımında hata var mı?)
En az kaç kapıdan geçerek?
Hiçbir yerden ulaşılamayan, boşa tasarlanmış oda var mı?

Odaları noktalar, kapıları çizgiler olarak çizin: bu bir graf. Üç sorunun da cevabı bu sunumda.

Mini sözlük

graph · vertex · edge	graf · düğüm (köşe) · kenar	Noktalar ve onları ikişer ikişer bağlayan çizgiler
adjacent · degree	komşu · derece	Kenarla bağlı iki düğüm · bir düğüme değen kenar sayısı
path · cycle	yol · döngü	Kenarlarla birbirine bağlı düğüm dizisi · başladığı yere dönen yol
connected component	bağlı bileşen	Birbirine yolla ulaşılabilen düğümlerin en büyük grubu
DFS · BFS	derinlik / genişlik öncelikli arama	Grafı gezmenin iki temel yolu
adjacency list	komşuluk listesi	Her düğüm için komşularının listesi
sparse · dense	seyrek · yoğun	Kenar sayısı V’ye yakın · V²’ye yakın

📜 Her şey bir yürüyüşle başladı: Königsberg, 1736

Königsberg şehrinde (bugün Kaliningrad) nehrin ortasında iki ada ve 7 köprü vardı. Halkın sorusu: “Her köprüden tam bir kez geçen bir yürüyüş var mı?”

Leonhard Euler haritayı attı ve sadece önemli olanı tuttu: 4 kara parçası (düğüm), 7 köprü (kenar). İlk graf!

Cevap: Hayır. Böyle bir yürüyüş için en fazla 2 kara parçasının köprü sayısı (derecesi) tek olabilir. Königsberg’de dördü de tek!

🎮 “Kalemi kaldırmadan çiz” bulmaca oyunları (Euler yolu) tam bu kurala göre tasarlanır.

LEVEL 0

Terimler

graf dilini öğrenelim

terimler
gösterimler
DFS
BFS
bağlı bileşenler
oyunda graflar ve zor problemler

Graf terimleri

Yol: 0 – 6 – 4 – 3 (kenarlarla bağlı düğümler)
Döngü: 0 – 5 – 4 – 6 – 0 (başladığı yere dönen yol)
Derece: 0’ın derecesi 4 (4 komşusu var)
Bağlı: 0’dan 3’e yol var → bağlılar. 0’dan 9’a yol yok.
Bağlı bileşen: bu grafın 3 bileşeni var: {0…6}, {7, 8}, {9…12}

Animasyon 0’dan DFS yapıyor: 9–12 grubuna hiç ulaşamayacak. (DFS’yi birazdan ayrıntılı göreceğiz.)

🎮 Oyunlarda graflar her yerde

oyun / sistem	düğüm	kenar
Zindan / metroidvania haritası	oda	kapı / koridor
Risk, Civilization, strateji haritaları	bölge / ülke	ortak sınır
Karo (tile) tabanlı harita	yürünebilir kare	komşu kare (4 ya da 8 yön)
3B oyunlarda yol bulma	navmesh çokgeni / yol noktası (waypoint)	geçilebilir sınır
Arkadaş listesi, klanlar	oyuncu	arkadaşlık
Bulmaca / satranç arama	oyun durumu	bir hamle

Arkadaşlık “karşılıklı” → yönsüz kenar. “Takip ediyor”, “tek yönlü kapı”, “önce bu görev” → yönlü (sonraki sunum).

🎬 Ara: Königsberg’in yedi köprüsü

How the Königsberg bridge problem changed mathematics
TED-Ed (Dan Van der Vieren) · 4 dk 39 sn · YouTube’da aç

Graf kuramı 1736’da bir şehir bulmacasıyla doğdu: yedi köprünün her birinden bir kez geçerek dolaşılabilir mi? Euler haritayı düğüm ve kenara indirgedi; biz de oyun haritalarını öyle göreceğiz.

🤔 İzlerkenEuler haritadan hangi bilgileri attı, hangilerini tuttu? Cevap neden “hayır” çıktı? Bir oyun haritasında “her yoldan bir kez geçen tur” sorusu nerede karşımıza çıkabilir?

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

📊 Graf gösterimleri

VisuAlgo (NUS)

Aynı grafı komşuluk matrisi, komşuluk listesi ve kenar listesi olarak yan yana gösterir; grafı kendiniz çizebilirsiniz.

📊 DFS, BFS, topolojik sıralama

VisuAlgo (NUS)

Graf gezintilerini ve yığın/kuyruk içeriğini adım adım gösterir.

🔴 Flow Field Pathfinding (kule savunması)

Red Blob Games (Amit Patel)

Tek bir BFS ile bütün düşmanlara yol bulmak: haritaya tıklayıp hedefi değiştirin, oklar anında güncellenir.

🔴 Grids and Graphs

Red Blob Games (Amit Patel)

Izgaranın bir graf olduğunu ve komşuların nasıl bulunduğunu çizimlerle anlatır.

Quiz 1 · terimler

Bir grafta bütün düğümlerin derecelerini toplarsanız ne bulursunuz? (E = kenar sayısı)

Her kenarın iki ucu var ve her uç bir düğümün derecesine 1 ekliyor → toplam = 2E (“tokalaşma lemması”). Sonuç: derecesi tek olan düğümlerin sayısı hep çifttir. Euler’in Königsberg kanıtı da bu tür bir sayma.

LEVEL 1

Gösterimler

grafı bellekte nasıl tutarız?

terimler
gösterimler
DFS
BFS
bağlı bileşenler
oyunda graflar ve zor problemler

Üç gösterim — kendiniz karşılaştırın

Hangisi?

gösterim	bellek	kenar ekle	v–w kenarı var mı?	v’nin komşularını gez
kenar listesi	E	1	E	E
komşuluk matrisi	V²	1	1	V
komşuluk listeleri	E + V	1	derece(v)	derece(v)

Gerçek graflar seyrekBir oyun haritasında 10.000 kare var ama her karenin en fazla 4–8 komşusu. Matris: 100 milyon hücre, neredeyse hepsi 0 (Sembol Tablosu Uygulamaları sunumundaki seyrek matris!). Liste: ~40.000 kayıt.

⚙️ Karo haritalar: örtük grafIzgarada komşuluk listesi bile tutmayız: komşular hesaplanır (sağ, sol, üst, alt). Grafın kendisi hiç bellekte yoktur — implicit graph.

Graf sınıfı — komşuluk listeleri

Graph API’si:

Graph(V)	V düğümlü, kenarsız graf
addEdge(v, w)	v–w kenarı ekle
adj(v)	v’nin komşuları
V() · E()	düğüm · kenar sayısı

🎒 Liste listesiadj[v] bir liste; adj bu listelerin listesi. Düğümler 0…V−1 numaralı → dizi indeksi olarak kullanılır. Adlı düğümler (“Mağara”, “Köy”) için önce bir sözlükle isim → numara (önceki sunum!).

🎒 [[] for v in range(V)]: V tane ayrı boş liste. ⚠️ [[]] * V yazmayın: V kez aynı listeyi gösterir — bir düğüme eklenen komşu hepsinde görünür! JS’teki Array.from({length: V}, () => []) aynı sebeple new Array(V).fill([]) yerine kullanılır.

🎮 Örtük graf: karo haritada komşular

🎒 yield (Python): fonksiyon bir liste kurmak yerine değerleri tek tek üretir (üreteç). Geleneksel hâli: boş liste + append + return (C# ve JS sekmelerindeki gibi). Haritanın kenarı duvar olduğu için dizi dışına çıkmıyoruz.

🔗 Ayrıntısı: Y8 · A* (ızgara, waypoint ve navmesh gösterimleri) sunumunda.

Quiz 2 · gösterimler

100 × 100’lük bir karo haritası (10.000 kare, 4 yönlü komşuluk) için komşuluk matrisi kaç hücre tutar?

Matris V × V = 10.000² = 100 milyon hücre; bunların sadece ~40.000’i 1. Komşuluk listeleri ~V + 2E ≈ 50.000 kayıt; örtük ızgara ise hiç ek bellek tutmaz.

LEVEL 2

DFS

depth-first search — labirentte ip çözmek

terimler
gösterimler
DFS
BFS
bağlı bileşenler
oyunda graflar ve zor problemler

Problem: çıkışa yol var mı? İlk akla gelenler

Komşu listeleri: 0: [1, 2] · 1: [2, 0] · 2: [0, 1, 3] · 3: [2, 4]

1. deneme: “hep ilk komşuya git.” 0’dan 1’e, 1’den 2’ye, 2’nin ilk komşusu 0… Kırmızı daire: aynı üç oda arasında sonsuza dek döner, çıkışın bir oda ötede olduğunu hiç görmez.

2. deneme: “bütün yolları dene.” Döngü yoksa çalışır ama yol sayısı patlar: 10 × 10’luk açık bir ızgarada köşeden köşeye kendini kesmeyen yol sayısı 10²⁰’nin üstünde. Her birini denemek evrenin ömrünü aşar.

Çözüm: gittiğin odayı işaretle. İşaretli bir odaya bir daha girme. Her oda en çok bir kez ziyaret edilir, her koridor en çok iki kez bakılır: döngü de patlama da biter. Bu kurala uyan sistematik yürüyüşün adı derinlik öncelikli arama (DFS). Theseus’un ipi ve Trémaux’nun tebeşiri aynı fikir (sonraki slayt).

Labirent keşfi: Trémaux ve Theseus

Yunan mitolojisinde Theseus, Minotor’un labirentine bir ip yumağı ile girer:

Gittiğin her koridoru işaretle (ipi çöz)
İşaretsiz bir koridor varsa ona dal
Çıkmaza girersen ip boyunca geri dön backtrack ve başka bir işaretsiz koridor dene

Bu, derinlik öncelikli aramadır (DFS): olabildiğince derine git, sonra geri dön. 19. yüzyılda Fransız matematikçi Trémaux da tebeşirle aynı yöntemi tarif etti.

🎮 OyundaRastgele labirent üretmenin en popüler yolu “rastgele DFS”dir: işaretsiz komşulardan rastgele birine git, duvarı yık. (Haritadaki 🌀 Labirent düğmesi tam bunu yapıyor.) Uzun, kıvrımlı koridorlar onun imzasıdır.

DFS — iz tablosu

Mavi = işaretli (çağrı yığınında), yeşil = bitti, sarı = şu anki. Kesikli = bakılan kenar. Tablodaki edgeTo[w] = v: “w’ye ilk kez v’den geldim”. Kaynağı değiştirmek için bir düğüme tıklayın.

DFS — kod (1/2)

DFS — kod (2/2)

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`marked[v] = true`	bu odaya geldim	önce işaretle, sonra komşulara bak: yoksa döngüde aynı odaya tekrar girilir
`if (!marked[w])`	yalnızca gidilmemiş komşulara in	her oda bir kez ziyaret edilir → toplam iş ~V + E
`edgeTo[w] = v`	w’ye v’den geldim	yolu sonradan geri izlemek için “ekmek kırıntısı”; bir ağaç oluşturur
`dfs(w)` (özyineleme)	w’nin içine dal, bitince v’ye dön	dönüş = geri gelmek; çağrı yığını bizim yerimize “geldiğimiz yolu” tutar
`pathTo(v)`	v’den s’ye edgeTo’yu izle, ters çevir	DFS yolu bulur ama en kısa yolu garanti etmez (BFS’e kadar bekleyin)

DFS ne kadar sürer? Ve bir uyarı

ÖnermeDFS, s’ye bağlı bütün düğümleri, derecelerinin toplamıyla orantılı sürede işaretler (≤ V + 2E).

Her düğüm bir kez işaretlenir; her kenara iki kez (iki ucundan) bakılır. edgeTo[] ile s’den her ulaşılan düğüme bir yol bulunur — ama en kısa olması gerekmez!

⚙️ Özyineleme derinliğiDFS’de çağrı yığını ulaşılan yol kadar derinleşebilir. 1000 × 1000’lik bir karo haritasında yol 1 milyon kare olabilir → yığın taşması stack overflow (Python’da sınır ~1000!).

Çözüm: özyineleme yerine açık bir yığın (Yığınlar sunumu) kullanın. Oyun motorlarında flood fill hep böyle yazılır.

Quiz 3 · DFS

DFS ile bulunan pathTo(v) yolu için hangisi doğrudur?

edgeTo zinciri gerçek kenarlardan oluşur → yol geçerli. Ama DFS “olabildiğince derine” gittiği için dolambaçlı bir yol bulabilir. En kısa yol (en az kenar) için BFS gerekir — sıradaki konu.

LEVEL 3

BFS

breadth-first search — önce yakınlar, sonra uzaklar

terimler
gösterimler
DFS
BFS
bağlı bileşenler
oyunda graflar ve zor problemler

BFS: suya atılan taş 🌊

Kaynağı işaretle, kuyruğa koy
Kuyruktan bir düğüm çıkar
İşaretsiz komşularının hepsini işaretle, edgeTo’larını yaz, kuyruğa koy
Kuyruk boşalana kadar tekrarla

Neden en kısa?Kuyruk (FIFO) sayesinde düğümler uzaklık sırasıyla çıkar: önce 1 adımdakilerin hepsi, sonra 2 adımdakiler… Bir düğüme ilk ulaştığımız an, oraya ulaşmanın en kısa yolunu bulmuşuzdur.

DFS ile tek fark: yığın yerine kuyruk! (Yığınlar ve Kuyruklar sunumundaki flood fill demosunu hatırlayın.)

BFS — iz tablosu

Mor kesikli = kuyrukta bekleyen. Mor rozet = kaynağa uzaklık (distTo). Bütün kenarları kenar sayısına göre en kısa yollardan oluşan yeşil ağaç: en kısa yollar ağacı.

BFS — kod

🎒 Python list.pop(0) ve JS shift() diziyi kaydırır → O(N) (Bağlı Listeler sunumu!). deque ya da “baş işaretçisi” hilesi O(1).

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`q = [s]; head = 0`	kuyruk: dizi + baş işaretçisi	`shift()` her seferinde bütün diziyi kaydırır; işaretçi sabit iş
`marked[w] = true` (kuyruğa koyarken)	w’yi görür görmez işaretle	çıkarırken işaretlersek aynı oda kuyruğa birkaç kez girer
`distTo[w] = distTo[v] + 1`	w, v’den bir adım uzakta	kuyruk mesafeye göre sıralı ilerler: önce bütün 1’ler, sonra 2’ler…
`edgeTo[w] = v`	w’ye v’den geldim	BFS ağacında kökten her düğüme giden yol en kısa yoldur (kenar sayısı olarak)
döngü koşulu `head < q.length`	kuyruk boşalana kadar	s’den ulaşılabilen her oda tam bir kez çıkar: ~V + E

🎮 Haritada BFS ve DFS yarışı

Algoritmayı değiştirip tekrar arayın: BFS dalga gibi yayılır ve en kısa yolu bulur; DFS koridor koridor dalar ve uzun, dolambaçlı bir yol bulur. Fareyle duvar çizin, 🌀 labirent deneyin.

🔗 Ayrıntısı: Y8 · A* (dört algoritmanın yarışı) sunumunda.

Kaç adımda tanışıyoruz? (“Kevin Bacon sayısı”)

Klasik örnek: aktörler ve filmler grafında herkesin Kevin Bacon’a uzaklığı (BFS). Burada bir oyun arkadaşlık ağı: “Pro Oyuncu” ile aranızda kaç kişi var? Rozet = uzaklık.

Quiz 4 · BFS

BFS’de bir düğüme ilk kez ulaşıldığında bulunan uzaklık neden kesinlikle en kısadır?

Kuyrukta her an en fazla iki farklı uzaklık vardır: k ve k+1, ve k’lar önde. Bir düğüme daha kısa bir yol olsaydı, o yolun önceki düğümü daha erken işlenir ve düğümü daha önce işaretlerdi.

LEVEL 4

Bağlı bileşenler

connected components — kaç ayrı parça var?

terimler
gösterimler
DFS
BFS
bağlı bileşenler
oyunda graflar ve zor problemler

Kaç ada var? 🏝️

Algoritma: bütün kareleri sırayla gez; işaretsiz bir kara bulunca oradan DFS yap ve ulaşılan her kareye aynı numarayı (id[]) ver. Bu, resim programlarındaki “boya kovası” flood fill aracının kendisi.

Bağlı bileşenler — kod

id[v] = v’nin bileşen numarası
connected(v, w) = id[v] == id[w] → O(1)!
Toplam süre: V + E (her düğüm bir kez işaretlenir)

Union–Find ile karşılaştırma (Ders 1!)

DFS: graf baştan belli → bir kez V + E, sonra her soru O(1)
Union–Find: kenarlar tek tek geliyor (çevrimiçi) → her kenar ~sabit; graf değişirken soruları yanıtlar

🎮 Prosedürel seviye doğrulama

Rastgele üretilen bir mağara/zindan haritası oynanabilir mi? Bağlı bileşenleri hesapla:

Giriş, çıkış ve bütün hazineler aynı bileşende mi? Değilse haritayı reddet ya da bileşenleri bir koridorla bağla.
Çok küçük bileşenler (2–3 karelik kapalı ceplere) → doldur, duvar yap.
En büyük bileşeni “ana mağara” olarak tut — hücresel otomat (cellular automata) mağara üreticilerinin standart son adımı.

Aynı fikir Minecraft benzeri oyunlarda “ışık/su yayılması”, Go ve “Bejeweled” türü oyunlarda “bağlı taş grupları” için de kullanılır.

Quiz 5 · bağlı bileşenler

Bağlı bileşenler bir kez hesaplandıktan sonra “v ile w arasında yol var mı?” sorusu ne kadar sürer?

Ön işleme (DFS ile id[] hesaplamak) V + E sürer, ama sonra her soru tek bir karşılaştırma. Bu “önce hazırlan, sonra hızlı cevapla” kalıbı graf algoritmalarında çok yaygın.

LEVEL 5

Oyunda graflar ve zor problemler

hangi graf problemleri kolay, hangileri imkânsız derecede zor?

terimler
gösterimler
DFS
BFS
bağlı bileşenler
oyunda graflar ve zor problemler

Graf problemleri zorluk tablosu

problem	🎮 oyundaki karşılığı	zorluk
s’den t’ye yol var mı?	boss odasına ulaşılabilir mi?	kolay: DFS/BFS
en az kenarlı yol	en az kapıdan geçen rota	kolay: BFS
döngü var mı?	harita bir ağaç mı (tek yol), yoksa alternatif rotalar var mı?	kolay: DFS
iki parçalı mı? bipartite	rakipler aynı takıma düşmeden iki takıma bölünebilir mi?	kolay: DFS ile 2 renge boya
Euler turu	her koridordan tam bir kez geç (“kalemi kaldırmadan çiz”)	kolay: derece kuralı
Hamilton turu	her odaya tam bir kez uğra / gezgin satıcı	çok zor (NP-tam)
en uzun basit yol	“en uzun koşu rotası”	çok zor (NP-tam)
iki graf aynı mı? isomorphism	iki prosedürel harita aslında aynı yapıda mı?	bilinmiyor!

Euler ve Hamilton birbirine çok benziyor (kenarlar mı, düğümler mi?) ama biri lise matematiği, öteki bilgisayar biliminin en ünlü çözülmemiş sorusunun (P = NP?) bir parçası.

🧪 Kod laboratuvarı: BFS ile uzaklıklar

Bu kod tek bir şeyi yanlış yapıyor: adı “stack” olan şey ve pop()… Bazı graflarda uzaklıklar fazla çıkıyor. Neden? (İpucu: DFS mi BFS mi oldu?) Kuyruğa çevirin: shift() ya da baş işaretçisi.

🐍 Kod laboratuvarı — adaları say (Python)

Şu an her kara karesini ayrı ada sayıyor. Bir kara bulunca, ona bağlı bütün karaları bir yığınla (DFS) gezip '.' yapın (“batırın”) ki bir daha sayılmasın. Sınır kontrolünü unutmayın: 0 <= nr < R.

Derin hikâye: Altı adım mı, üç buçuk adım mı?

1967: sosyal psikolog Stanley Milgram, ABD’nin ortasındaki (Nebraska ve Kansas) gönüllülere, Boston’daki bir hedef kişiye ulaştırılmak üzere mektuplar verdi. Kural: mektubu sadece adıyla tanıdığınız, hedefe daha yakın olduğunu düşündüğünüz birine gönderin.
Hedefe ulaşan mektuplar ortalama 5–6 aracıdan geçti: “altı derece ayrılık” fikri buradan yayıldı. (Ulaşamayan çok sayıda mektup da vardı; deney yöntemi bu yüzden tartışıldı.)
2016: Facebook araştırmacıları, yaklaşık 1,6 milyar kullanıcının arkadaşlık grafında iki kişi arasındaki ortalama uzaklığı 3,57 adım olarak hesapladı. Bu ölçekte her çift için BFS mümkün değil; uzaklık dağılımını tahmin eden algoritmalar kullanıldı.

Ders“Kaç adımda ulaşırım?” sorusu, ağırlıksız bir graf üzerinde BFS’in tanımıdır. Gerçek sosyal ağlar “küçük dünya”dır: düğüm sayısı devasa olsa da uzaklıklar küçük. Oyunlarda NPC ilişkileri, söylentilerin yayılması (Y14’teki Smallville), harita bağlantılılığı aynı yapıdadır.

Kaynak: Wikipedia: Small-world experiment · Facebook Research 2016

🧰 Kütüphaneler ve araçlar

ad	platform	ne yapar / sınırları	nasıl eklenir
NetworkX	Python	Graf oluşturma, BFS/DFS, bağlı bileşenler, en kısa yol, çizim. Öğrenme ve analiz için ideal; çok büyük graflarda yavaş.	`pip install networkx`
igraph	Python / R / C	Büyük graflar için hızlı C çekirdeği.	`pip install igraph`
scipy.sparse.csgraph	Python	Seyrek matris üzerinde BFS, bağlı bileşenler, en kısa yollar.	`pip install scipy`
QuikGraph	C#	.NET için graf kütüphanesi (QuickGraph’ın devamı): aramalar, bileşenler, en kısa yol.	NuGet: `QuikGraph`
Graphology	JavaScript	Graf veri yapısı ve standart algoritmalar; Sigma.js ile görselleştirme.	`npm install graphology`

🧩 Oyunlarda yönsüz graflar

Harita bağlantılılığı: prosedürel seviyede başlangıçtan çıkışa yol var mı? (BFS / flood fill, Y15)
Bölge etiketleme: mayın tarlasında boş alanın açılması, boya kovası, mağara cepleri.
Sosyal graf: NPC ilişkileri, söylentinin kaç adımda yayıldığı.
Gösterim seçimi: ızgarada komşuluk örtük (komşuları hesaplayın, saklamayın); seyrek graflarda komşuluk listesi; çok küçük ve yoğun graflarda matris.

BFS/DFS tuzakları

“Ziyaret edildi” işaretini kuyruğa eklerken koyun; çıkarırken koyarsanız aynı düğüm defalarca eklenir.
Büyük haritada özyinelemeli DFS → yığın taşması: açık bir yığın kullanın.
Izgara sınırlarını kontrol etmeyi unutmak.
Yönsüz kenarı tek yönde eklemek.

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

Ziyaret işaretini kuyruktan çıkarırken koymak
Büyük haritada özyinelemeli DFS
Izgara sınır kontrolünü unutmak
Yönsüz kenarı tek yönlü eklemek

İyi bir istek (prompt) örneği

“Unity 6, C#. Tilemap tabanlı bir haritada bölge etiketleme yaz: duvar olmayan hücreleri 4-komşulukla BFS ile bölgelere ayır (int[,] etiket dizisi), her bölgenin boyutunu ve sınır kutusunu döndür, en büyük bölge dışındakileri isteğe bağlı olarak duvarla doldur. Özyineleme kullanma; Queue kullan. Mayın tarlası tarzı “boş alanı aç” fonksiyonunu da aynı BFS ile yaz ve NUnit testleri ekle.”

Gösterimi (örtük ızgara, liste, matris) belirtin
Ziyaret işaretinin nerede konduğunu açıklatın
Özyinelemesiz DFS isteyin
Sınır durumları (tek hücre, hiç yol yok) test ettirin

🚀 Proje ve araştırma önerileri

[kolay] Mayın tarlası — Boş hücreye tıklayınca BFS ile bölgeyi açan klasik oyun.
[orta] Bağlantı kontrollü seviye üreteci — Y15’teki mağara üretecine BFS ile bağlantı kontrolü ve onarım ekleyin.
[orta] NPC sosyal ağı — Köydeki NPC’lerin arkadaşlık grafında bir söylentinin yayılmasını BFS seviyeleriyle canlandırın.
[araştırma] Küçük dünya — Watts–Strogatz modeliyle graflar üretip ortalama uzaklığı ve kümelenmeyi ölçün.

📄 Akademik okumalar ve kaynaklar

Travers & Milgram 1969 · An Experimental Study of the Small World Problem (Sociometry 32(4))
Altı derece deneyi.

Watts & Strogatz 1998 · Collective Dynamics of “Small-World” Networks (Nature 393)
Küçük dünya ağları modeli.

Backstrom ve ark. 2012 · Four Degrees of Separation (WebSci 2012)
Facebook grafında uzaklık ölçümü.

Neler öğrendik? 🎒

Graf = düğümler + kenarlar; oyun haritaları, ağlar, durumlar.
Komşuluk listeleri: V + E bellek; seyrek graflar için ideal. Karo haritalar örtük graf.
DFS: yığın / özyineleme; erişilebilirlik, yol, bileşenler, döngü.

BFS: kuyruk; en az kenarlı (en kısa) yollar.
Bağlı bileşenler: id[] ile O(1) “bağlı mı?”.
Bazı graf problemleri kolay, bazıları (Hamilton) imkânsız derecede zor.
🎮 Seviye doğrulama, labirent üretimi, ada sayma, arkadaş uzaklığı.

Alıştırmalar 🏋️

Kâğıt-kalem: tinyCG’de 3’ten başlayarak DFS ve BFS iz tablolarını çıkarın (komşuluk listesi sırası: slayttaki gibi).
Graf yönsüzse, DFS ile döngü olup olmadığını nasıl anlarsınız? (İpucu: işaretli bir komşu, geldiğin düğüm değilse…)
p5.js’te bir karo haritası çizin; tıklanan kareden BFS yapıp her karenin uzaklığını sayı olarak yazdırın. Fare hedefi gösterince yolu çizin.
“İki takıma bölme” (bipartite) kontrolünü DFS ile yazın: her düğümü komşusunun tersi renge boyayın; çelişki çıkarsa bölünemez.
Hücresel otomat ile bir mağara üretin; bağlı bileşenleri bulun ve en büyüğü dışındakileri duvarla doldurun.
🤖 Bir YZ asistanından Python’da BFS isteyin. Kuyruk için list.pop(0) mı, deque mu kullandı? 1 milyon düğümde fark nedir?

🎮 Bu sunumdaki oyunlar

Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.

Civilization 1991– · sıra tabanlı strateji

Bir uygarlığı taş devrinden uzay çağına yönetirsiniz; teknoloji ağacı serinin simgesi.

📖 Fandom wikisi · ▶ video 2:45

Minecraft 2011 · kum havuzu

Bloklardan oluşan, prosedürel üretilen, neredeyse sonsuz bir dünya.

📖 Minecraft Wiki · 🎯 dünya üretimi · ▶ video 1:01