---
title: "Çizgeler ve Enine Arama (BFS)"
subtitle: "Çizge G=(V,E), yönlü (sıralı) / yönsüz (sırasız); basit çizgede |E|=O(V²); derece toplamı 2|E| → komşu döngüsü O(E); komşuluk listesi (+hash) O(1) kenar sorgusu; en kısa yol ağacı = öncül P(v), O(V) yer (optimal alt yapı); BFS seviye kümeleri Lₖ katman katman → δ/P/L tek geçişte, O(V+E) doğrusal"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Solomon'un videosu:** [YouTube — Lecture 9: Breadth-First Search](https://www.youtube.com/watch?v=oFVYVzlvk9c) (≈53 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 9: Breadth-First Search](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-9-breadth-first-search/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 13 (L9)
- **Hoca:** Justin Solomon (Demaine/Ku değil)
- **Okuma süresi:** ≈25 dk
> Bu ders, kursun **çizge (graph) ünitesinin açılışıdır** — veri yapılarından çizge algoritmalarına geçiş.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d13}
Ders 12 (L8) ikili yığınla öncelik kuyruğunu çözdü. Bugün Justin Solomon ile kursun **ikinci bölümünü** açıyoruz: **çizge algoritmaları**. Önce çizge terminolojisini kurarız (düğüm, kenar, yönlü/yönsüz), sonra bir kaynaktan **tüm düğümlere en kısa yolu** hesaplayan ilk algoritmayı veririz: **enine arama (BFS, breadth-first search)**.
> *"we're officially starting part two of this class... our new unit which is graph theory."* — Solomon, 0:57
Üç temel kavram bu derste yan yana gelir:
1. **Çizge ve gösterimi** — $G = (V, E)$; komşuluk listesi (adjacency list) ile $O(1)$ kenar sorgusu.
2. **En kısa yol ağacı** — her düğümde sadece "öncül" $P(v)$ tutarak yolu $O(V)$ yerde sakla.
3. **BFS** — seviye kümelerini (level sets) katman katman üreterek ağırlıksız en kısa yolu $O(V + E)$'de bul.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 13'ün (L9) kavram haritası: kök = çizgeler ve enine arama. Dört dal — (1) çizge G=(V,E), düğüm + kenar; kenar yönlü (sıralı çift) ya da yönsüz (sırasız küme); basit çizgede |E| = O(V²). (2) gösterim: komşuluk listesi düğümü komşularına eşler, hash ile beklenen O(1) kenar sorgusu; kenar listesi O(E), komşuluk matrisi O(V²) yer. (3) en kısa yol ağacı: her düğümde yalnız öncül P(v) tutulur, yol geriye izlenerek kurulur, O(V) yer (optimal alt yapı). (4) BFS: seviye kümeleri Lₖ katman katman üretilir, δ ve öncül tek geçişte dolar, doğrusal zaman O(V+E). Sonuç: bağlı her şeyin evrensel soyutlaması + ağırlıksız en kısa yol."
flowchart TD
A["Ders 13 (L9): Çizgeler ve Enine Arama"] --> G["Çizge G=(V,E)<br/>düğümler + kenarlar"]
G --> G1["yönlü (sıralı çift)<br/>yönsüz (sırasız küme)"]
G --> G2["basit çizge<br/>derece toplamı = iki kat kenar"]
A --> R["Gösterim<br/>komşuluk listesi (hash)"]
R --> R1["kenar sorgusu beklenen sabit<br/>kenar listesi yavaş, matris savurgan"]
A --> P["En kısa yol ağacı<br/>öncül P(v)"]
P --> P1["yolu geriye izle<br/>az yer, optimal alt yapı"]
A --> B["BFS<br/>seviye kümeleri katman katman"]
B --> B1["dalga dalga yayılma<br/>doğrusal zaman, ağırlıksız en kısa yol"]
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
class A root
class G,R,P,B branch
class G1,G2,R1,P1,B1 leaf
```
::: {.callout-tip title="Builder Notu — Bağlı Her Şey Bir Çizgedir"}
Çizge, "birbirine bağlı her şeyin" evrensel soyutlamasıdır — ağ topolojisi, sosyal graf, bağımlılık grafı, durum-geçiş uzayı. Önce nasıl saklayacağını (gösterim), sonra nasıl gezeceğini (BFS) sorarız.
- **Geriye → Ders 2-5 (veri yapıları):** çizge de bir veri yapısı tasarım problemi; "hangi sorguyu hızlandıracağım?" sorusu gösterim seçimini (kenar listesi / komşuluk listesi / matris) belirler.
- **Geriye → Ders 8 (PS3, reduction):** üç çizge problemi (erişilebilirlik ⊂ tek-çift en kısa yol ⊂ tek-kaynak en kısa yol) birbirine *indirgenir* — birini çözen diğerini çözer.
- **İleriye → Ders 16-19 (L11-L13, Dijkstra):** BFS, ağırlıksız en kısa yoldur; ağırlıklara geçince öncelik kuyruğu (yığın) devreye girer (PS5 = Ders 17 arada).
- **İleriye → her yer:** ağ yönlendirme (router, Google Maps), sosyal ağ, durum-geçiş (Rubik küpü), 3B model (üçgen ağ), seçim bölgesi — hepsi çizge.
Tek cümle: *Çizgeyi komşuluk listesiyle saklayıp BFS ile katman katman gezersek, bir kaynaktan tüm düğümlere ağırlıksız en kısa yolu $O(V + E)$'de buluruz — ve sadece "öncül"leri tutarak yolları $O(V)$ yerde saklarız.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 13 (L9) Çizge + BFS motoru (_engine.py D13 bölümü:
# bfs'ten brute_shortest_paths'e) + Slate+Amber viz (_viz.py COL_* + apply_style).
# Bu hücre gizlidir (#| echo: false). Aşağıdaki TÜM figür hücreleri bu hücrede
# tanımlanan bfs / bfs_levels / bfs_trace / reconstruct_path / degree_sums /
# make_undirected / make_directed / build_example_graph / brute_shortest_paths
# + COL_* / apply_style'ı IMPORT ETMEDEN kullanır.
#
# Notion'daki öğretim içeriği (görünür ```python blokları) bu motorun tarif
# seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir). Standalone testte savefig
# kullanılır; Quarto render'da jupyter inline backend'i ayarlar.
# Yalnız D13 gerekenler gömülür (collections.deque importu dahil).
# ============================================================================
import math
from collections import deque
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyBboxPatch, FancyArrowPatch, Arc
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir) + apply_style
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
def apply_style(ax):
"""Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için)."""
ax.set_facecolor(COL_WHITE)
ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8)
for spine in ax.spines.values():
spine.set_color(COL_SLATE_400)
ax.tick_params(colors=COL_TEXT)
ax.title.set_color(COL_TEXT)
ax.xaxis.label.set_color(COL_TEXT)
ax.yaxis.label.set_color(COL_TEXT)
return ax
# ---------------------------------------------------------------------------
# _engine.py D13 (L9) — Çizgeler ve Enine Arama (BFS). Temsil:
# adj = dict {düğüm: komşu listesi} (yönlü: yalnız çıkış komşuları).
# ---------------------------------------------------------------------------
def bfs(adj, s):
"""BFS (L9 §8): kaynaktan katman katman; (delta, parent) döndürür.
'Henüz görülmemiş' kontrolü ilk (= en kısa) uzaklığı sabitler. O(V+E)."""
delta = {s: 0}
parent = {s: None}
queue = deque([s])
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in delta: # henüz görülmemiş
delta[v] = delta[u] + 1
parent[v] = u
queue.append(v)
return delta, parent
def bfs_levels(adj, s):
"""Seviye kümeleri (L9 §8): Lₖ = kaynaktan tam k uzaklıktaki düğümler.
Döndürür: [L0, L1, ...] (her Lᵢ sıralı liste — deterministik figür)."""
delta, _ = bfs(adj, s)
if not delta:
return []
kmax = max(delta.values())
return [sorted(v for v, d in delta.items() if d == k) for k in range(kmax + 1)]
def bfs_trace(adj, s):
"""fig-bfs-run için adım izi: her işlenen u'da (u, yeni eklenenler,
kuyruk durumu-sonrası, delta-anlık)."""
delta = {s: 0}
parent = {s: None}
queue = deque([s])
steps = []
while queue:
u = queue.popleft()
added = []
for v in adj[u]:
if v not in delta:
delta[v] = delta[u] + 1
parent[v] = u
queue.append(v)
added.append(v)
steps.append({"u": u, "added": added, "queue": list(queue),
"delta": dict(delta)})
return {"steps": steps, "delta": delta, "parent": parent}
def reconstruct_path(parent, s, t):
"""Öncül ağacından s→t yolu (L9 §7 / Egzersiz 5): P'yi geriye izle +
ters çevir. O(yol uzunluğu). t erişilemezse None."""
if t not in parent:
return None
path = [t]
while path[-1] != s:
path.append(parent[path[-1]])
path.reverse()
return path
def degree_sums(adj, directed=True):
"""Derece toplamı kimliği (L9 §4): Σ out-degree = |E| (yönlü);
yönsüz temsilde (her kenar iki listede) Σ degree = 2|E|.
Döndürür: (derece_toplamı, kenar_kaydı_sayısı)."""
total = sum(len(vs) for vs in adj.values())
return total, total # temsildeki kenar kaydı = toplam
def make_undirected(edges):
"""Yönsüz kenar listesi → komşuluk sözlüğü (her kenar iki yönde)."""
adj = {}
for u, v in edges:
adj.setdefault(u, []).append(v)
adj.setdefault(v, []).append(u)
for u in adj:
adj[u] = sorted(adj[u]) # deterministik gezinme
return adj
def make_directed(edges, vertices=()):
"""Yönlü kenar listesi → komşuluk sözlüğü (yalnız çıkış komşuları)."""
adj = {v: [] for v in vertices}
for u, v in edges:
adj.setdefault(u, []).append(v)
adj.setdefault(v, adj.get(v, []))
for u in adj:
adj[u] = sorted(adj[u])
return adj
def build_example_graph():
"""L9 figürleri için deterministik yönsüz örnek (7 düğüm, 8 kenar):
a - b seviyeler (kaynak a): L0={a}
| | L1={b, c}
c - d L2={d, e}
| | L3={f}
e - f - g L4={g}
"""
return make_undirected([("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"),
("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")])
def brute_shortest_paths(adj, s):
"""Bağımsız tanık (verify): seviye-seviye küme genişletme ile en kısa
mesafeler — BFS'ten FARKLI mekanizma (kuyruk yok, küme cebiri)."""
dist = {s: 0}
frontier = {s}
k = 0
while frontier:
k += 1
nxt = set()
for u in frontier:
for v in adj[u]:
if v not in dist:
nxt.add(v)
for v in nxt:
dist[v] = k
frontier = nxt
return dist
```
## 1. Çizge Nedir? {#sec-1-cizge-nedir}
Bir **çizge (graph)** $G = (V, E)$ iki şeyden oluşur: bir **düğüm (vertex)** kümesi $V$ ve bir **kenar (edge)** kümesi $E \subseteq V \times V$. Her kenar iki düğümü birbirine bağlar.
> *"a graph... is a collection of two things: a set of vertices and a set of edges."* — Solomon, 2:01
İki tür:
- **Yönlü (directed):** kenar bir *sıralı çift* $(w, v)$; $(w, v)$ ile $(v, w)$ **farklıdır** (su akışına karşı yüzemezsin).
- **Yönsüz (undirected):** kenar bir *sırasız küme* $\{v, w\}$; yön yoktur, yalnızca bağlantı.
> *"in a directed graph... the edge from w to v is different than the edge from v to w."* — Solomon, 3:53
@fig-graph-anatomy bu iki türü yan yana koyar: solda yönsüz kenar (sırasız küme $\{v, w\}$, oksuz), ortada yönlü kenar (sıralı çift $(w, v)$, oklu — $(v, w) \neq (w, v)$), sağda bu dersin örnek çizgesi (7 düğüm) derece rozetleriyle ve $\sum \deg(v) = 16 = 2|E|$ kimliğiyle.
```{python}
#| label: fig-graph-anatomy
#| fig-cap: "Çizge anatomisi: yönsüz {v,w} vs yönlü (w,v) + derece toplamı kimliği (L9 §1/§4). SOL panel — YÖNSÜZ mini çizge: kenar = SIRASIZ küme {v, w}; düz (oksuz) çizgi, {v,w} = {w,v} aynı kenardır. ORTA panel — YÖNLÜ mini çizge (aynı düğümler): kenar = SIRALI çift (w, v); oklu kenar, (v,w) ≠ (w,v) → çift-yön İKİ ayrı ok ile (amber vurgu). SAĞ panel — bu dersin örnek çizgesi (7 düğüm sabit yerleşim): her düğüm yanında derece rozeti a:2 b:2 c:3 d:3 e:2 f:3 g:1; c-d kenarı amber işaretli, iki ucuna +1 (kenar İKİ uçtan sayılır); alt kutu Σ deg(v) = 16 = 2|E| = 2·8. Bu kimlik 'her düğümün her komşusunu gez' döngüsünü TOPLAM O(E) yapar. Motor kanıtı: degree_sums(build_example_graph()) → 16; dereceler {a:2,b:2,c:3,d:3,e:2,f:3,g:1}; make_directed'da (v,w) ile (w,v) iki AYRI kenar (Solomon 2:01 / 3:53 / 17:37)."
#| fig-width: 11.0
#| fig-height: 6.4
# fig-graph-anatomy (L9 §1/§4): yönsüz vs yönlü kenar + Σ deg = 2|E| kimliği.
# Veri MOTORDAN (build_example_graph / degree_sums / make_directed). COL_* / plt
# gizli setup hücresinden. Çizge çizimi networkx KULLANMAZ — elle koordinat.
_GA_R = 0.30
def _ga_node(ax, x, y, label, fill=COL_BG, edge=COL_PRIMARY, lw=1.8,
tcol=COL_TEXT, r=_GA_R, zbase=5):
ax.add_patch(Circle((x, y), r, facecolor=fill, edgecolor=edge,
linewidth=lw, zorder=zbase))
ax.text(x, y, label, ha="center", va="center", fontsize=11.5,
color=tcol, weight="bold", zorder=zbase + 1)
def _ga_straight(ax, p0, p1, color=COL_SLATE_400, lw=1.6, z=1):
(x0, y0), (x1, y1) = p0, p1
dx, dy = x1 - x0, y1 - y0
d = math.hypot(dx, dy) or 1.0
ux, uy = dx / d, dy / d
ax.plot([x0 + ux * _GA_R, x1 - ux * _GA_R],
[y0 + uy * _GA_R, y1 - uy * _GA_R],
color=color, linewidth=lw, zorder=z, solid_capstyle="round")
def _ga_arrow(ax, p0, p1, color=COL_PRIMARY, lw=1.8, rad=0.0, z=2):
(x0, y0), (x1, y1) = p0, p1
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=14,
color=color, linewidth=lw, shrinkA=_GA_R * 72, shrinkB=_GA_R * 72,
connectionstyle=f"arc3,rad={rad}", zorder=z))
def _ga_panel_undirected(ax):
pos = {"v": (0.0, 1.0), "w": (1.6, 1.0), "x": (0.8, -0.15)}
for a, b in [("v", "w"), ("v", "x"), ("w", "x")]:
_ga_straight(ax, pos[a], pos[b], color=COL_PRIMARY, lw=1.9, z=1)
for name, (px, py) in pos.items():
_ga_node(ax, px, py, name, lw=1.9)
mx, my = (pos["v"][0] + pos["w"][0]) / 2, pos["v"][1] + 0.30
ax.text(mx, my, "{v, w}", ha="center", va="bottom", fontsize=10,
color=COL_AMBER_700, weight="bold", family="monospace")
ax.text(0.8, 1.95, "YÖNSÜZ çizge", ha="center", va="center",
fontsize=12, color=COL_TEXT, weight="bold")
ax.text(0.8, -0.95,
"kenar = SIRASIZ küme {v, w}\n{v, w} = {w, v} (tek kenar, oksuz)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", linespacing=1.4)
ax.set_xlim(-0.9, 2.5)
ax.set_ylim(-1.5, 2.3)
ax.set_aspect("equal")
ax.axis("off")
def _ga_panel_directed(ax):
pos = {"v": (0.0, 1.0), "w": (1.6, 1.0), "x": (0.8, -0.15)}
_ga_arrow(ax, pos["w"], pos["x"], color=COL_PRIMARY, lw=1.9, rad=0.0, z=2)
_ga_arrow(ax, pos["v"], pos["x"], color=COL_PRIMARY, lw=1.9, rad=0.0, z=2)
_ga_arrow(ax, pos["v"], pos["w"], color=COL_ACCENT, lw=2.2, rad=0.28, z=3)
_ga_arrow(ax, pos["w"], pos["v"], color=COL_AMBER_600, lw=2.2, rad=0.28, z=3)
for name, (px, py) in pos.items():
_ga_node(ax, px, py, name, lw=1.9)
ax.text(0.8, 1.62, "(v, w)", ha="center", va="center", fontsize=9.5,
color=COL_AMBER_700, weight="bold", family="monospace")
ax.text(0.8, 0.40, "(w, v)", ha="center", va="center", fontsize=9.5,
color=COL_AMBER_600, weight="bold", family="monospace")
ax.text(0.8, 1.95, "YÖNLÜ çizge", ha="center", va="center",
fontsize=12, color=COL_TEXT, weight="bold")
ax.text(0.8, -0.95,
"kenar = SIRALI çift (w, v)\n(v, w) ≠ (w, v) → çift-yön = İKİ ok",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", linespacing=1.4)
ax.set_xlim(-0.9, 2.5)
ax.set_ylim(-1.5, 2.3)
ax.set_aspect("equal")
ax.axis("off")
def _ga_panel_example(ax, deg_total, n_edges, deg):
base = {"a": (0.0, 2.0), "b": (1.0, 2.0), "c": (0.0, 1.0), "d": (1.0, 1.0),
"e": (0.0, 0.0), "f": (1.0, 0.0), "g": (2.0, 0.0)}
S = 1.65
pos = {k: (x * S, y * S) for k, (x, y) in base.items()}
edges = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"),
("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")]
marked = ("c", "d")
for a, b in edges:
hot = ({a, b} == set(marked))
_ga_straight(ax, pos[a], pos[b],
color=COL_ACCENT if hot else COL_SLATE_400,
lw=3.0 if hot else 1.7, z=2 if hot else 1)
for name, (px, py) in pos.items():
on_marked = name in marked
_ga_node(ax, px, py, name,
fill=COL_AMBER_100 if on_marked else COL_BG,
edge=COL_ACCENT if on_marked else COL_PRIMARY,
lw=2.6 if on_marked else 1.8)
bx, by = px + _GA_R + 0.10, py + _GA_R + 0.04
ax.add_patch(FancyBboxPatch(
(bx, by - 0.17), 0.62, 0.34,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_AMBER_100 if on_marked else COL_BG,
ec=COL_ACCENT if on_marked else COL_SLATE_400,
linewidth=1.8 if on_marked else 1.2, zorder=6))
ax.text(bx + 0.31, by, f"deg {deg[name]}", ha="center", va="center",
fontsize=7.6, color=COL_AMBER_700 if on_marked else COL_SLATE_500,
weight="bold", zorder=7)
cx0, cy0 = pos["c"]
cx1, cy1 = pos["d"]
midx, midy = (cx0 + cx1) / 2, (cy0 + cy1) / 2
for ex, ey in ((cx0, cy0), (cx1, cy1)):
ax.add_patch(FancyArrowPatch(
(midx, midy + 0.40), (ex, ey + 0.40),
arrowstyle="-|>", mutation_scale=11, color=COL_AMBER_700,
linewidth=1.6, connectionstyle="arc3,rad=0.0", zorder=5))
ax.text(midx, midy + 0.62, "+1", ha="center", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(midx, midy - 0.36, "bu kenar c VE d\nderecesine +1",
ha="center", va="center", fontsize=7.4, color=COL_AMBER_700,
style="italic", linespacing=1.3, zorder=6)
box_x, box_w = -0.35, 3.95
box_top, box_h = -0.95, 0.78
ax.add_patch(FancyBboxPatch(
(box_x, box_top - box_h), box_w, box_h,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=3))
ax.text(box_x + box_w * 0.5, box_top - box_h * 0.36,
f"Σ deg(v) = {deg_total} = 2|E| = 2·{n_edges}",
ha="center", va="center", fontsize=11.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(box_x + box_w * 0.5, box_top - box_h * 0.74,
"her kenar İKİ ucundan sayılır", ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=5)
ax.text((0.0 + 2.0 * S) * 0.5, 2.0 * S + 0.62, "örnek çizge (7 düğüm)",
ha="center", va="center", fontsize=12, color=COL_TEXT, weight="bold")
ax.set_xlim(-0.6, 2.0 * S + 0.95)
ax.set_ylim(box_top - box_h - 0.35, 2.0 * S + 0.95)
ax.set_aspect("equal")
ax.axis("off")
# ---- motor verisi + ASSERT (figür yalnız bunu çizer) ----
_ga_G = build_example_graph()
_ga_total, _ = degree_sums(_ga_G, directed=False)
_ga_E = _ga_total // 2
_ga_deg = {v: len(_ga_G[v]) for v in _ga_G}
assert _ga_total == 16 and _ga_E == 8, (_ga_total, _ga_E)
assert _ga_deg == {"a": 2, "b": 2, "c": 3, "d": 3, "e": 2, "f": 3, "g": 1}
_ga_D2 = make_directed([("v", "w"), ("w", "v")], vertices=("v", "w"))
assert _ga_D2["v"] == ["w"] and _ga_D2["w"] == ["v"] # iki AYRI kenar
fig, (axL, axM, axR) = plt.subplots(
1, 3, figsize=(11.0, 6.4), gridspec_kw={"width_ratios": [1.0, 1.0, 1.55]})
fig.patch.set_facecolor(COL_WHITE)
_ga_panel_undirected(axL)
_ga_panel_directed(axM)
_ga_panel_example(axR, _ga_total, _ga_E, _ga_deg)
fig.suptitle(
"Çizge anatomisi: yönsüz {v,w} vs yönlü (w,v) + derece toplamı kimliği",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985)
fig.text(0.5, 0.045,
"Σ deg(v) = 2|E| kimliği → her düğümün her komşusunu gezen döngü "
"TOPLAM O(E) iş yapar (her kenar iki kez ziyaret edilir)",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic")
plt.tight_layout(rect=(0.0, 0.06, 1.0, 0.95))
plt.show()
```
## 2. Çizgeler Her Yerde {#sec-2-cizgeler-her-yerde}
Birbirine bağlı her şey bir çizgedir: bilgisayar ağları (düğüm = makine, kenar = kablo), sosyal ağlar (düğüm = kişi, kenar = arkadaşlık), yol ağları (Google Maps en kısa yol çözer), Rubik küpü (düğüm = konfigürasyon, kenar = bir twist), 3B modeller (üçgen ağ), seçim bölgesi haritaları (komşuluk).
> *"graphs are literally everywhere in our everyday life."* — Solomon, 5:26
## 3. Basit Çizge ve |E| = O(V²) {#sec-3-basit-cizge}
Bu derste **basit çizge** varsayarız: özdöngü (self-loop) yok, her kenar farklı (çoklu kenar yok). Sonuç: kenar sayısı $|E| = O(V^2)$ (yönlü için $|E| \le 2 \binom{V}{2}$; yönsüz için $|E| \le \binom{V}{2}$; ikisi de en fazla $V^2$).
> *"the edges are big O of v squared."* — Solomon, 11:44
Bu yüzden çizge algoritmalarında **iki** boyut vardır: $V$ ve $E$. Bir çizge **seyrek (sparse)** ise ($E \ll V^2$), $E$'ye bağlı bir algoritma, $V^2$'ye bağlı olandan çok daha hızlı olabilir.
## 4. Komşular ve Derece {#sec-4-komsular-ve-derece}
- **Çıkış komşuları** $\text{Adj}^{+}(u)$: $u$'dan çıkan kenarların hedefleri. **Giriş komşuları** $\text{Adj}^{-}(u)$: $u$'ya giren kenarlar. (Yönsüzde ayrım yok, sadece $\text{Adj}(u)$.)
- **Derece (degree):** komşu kümesinin boyutu — çıkış derecesi (out-degree), giriş derecesi (in-degree).
> *"the out degree is the number of edges that point out of a vertex."* — Solomon, 17:37
Kritik kimlik (çizge algoritmalarında sürekli kullanılır): tüm düğümlerin derecelerinin toplamı $= 2|E|$ (yönsüz, her kenar iki düğüme sayılır) veya $|E|$ (yönlü, çıkış derecesi). Bu, "her düğüm için her komşusunu gez" döngüsünün $O(E)$ olduğunu söyler. Bu kimliği @fig-graph-anatomy'nin sağ panelinde somut olarak görmüştük: örnek çizgede $\sum \deg(v) = 16 = 2 \cdot 8$.
## 5. Çizge Veri Yapıları {#sec-5-cizge-veri-yapilari}
- **Kenar listesi (edge list):** tüm kenarların düz listesi. "$v \to w$ kenarı var mı?" sorgusu $O(E)$ — kötü.
- **Komşuluk listesi (adjacency list):** her düğüm $u$'yu, komşularına eşleyen bir küme. Komşu kümesini **hash tablosu** tutarsa, kenar sorgusu *beklenen* $O(1)$ (önce $u$'yu bul $O(1)$, sonra $w$'yi sorgula $O(1)$). $V^2 \to 1$.
> *"an adjacency list... a set that maps a vertex u to everything adjacent to u."* — Solomon, 23:08
- **Komşuluk matrisi (adjacency matrix):** $V \times V$ ikili dizi; kenar sorgusu $O(1)$ ama komşuları gezmek $O(V)$ ve $O(V^2)$ yer — büyük çizgeler için savurgan.
Genel kural: komşuluk listesi (+ hash) en dengeli seçim; gösterim, hangi sorguyu sık yapacağına bağlıdır.
@fig-representations aynı çizgeyi üç gösterimle yan yana koyar — kenar listesi (her sorguda yavaş), komşuluk listesi + hash (önerilen, amber çerçeve), komşuluk matrisi (sorgu hızlı ama yer ve komşu-gezme pahalı). Gösterim seçimi, hangi sorguyu hızlandıracağına bağlıdır.
```{python}
#| label: fig-representations
#| fig-cap: "Aynı çizge, üç gösterim: kenar listesi · komşuluk listesi · komşuluk matrisi (L9 §5, İMZA figür). Üstte referans çizge (7 düğüm, 8 yönsüz kenar). Altta 3 panel: (1) KENAR LİSTESİ — 8 kenarın düz listesi; 'a–g var mı?' sorgusu TÜM listeyi tarar → kenar sorgusu O(E), komşu gezme O(E), yer O(E) (slate ✗). (2) KOMŞULUK LİSTESİ + hash (ÖNERİLEN, amber çerçeve) — her düğüm → komşu kümesi; kenar sorgusu beklenen O(1), komşu gezme O(derece), yer O(V+E) (amber). (3) KOMŞULUK MATRİSİ — 7×7 ikili ızgara; kenar sorgusu O(1) AMA komşu gezme O(V) ve yer O(V²) (✗). Komşuluklar MOTORDAN: adj[a]={b,c}, adj[c]={a,d,e}, adj[f]={d,e,g}, adj[g]={f}; yönsüz kayıt 2|E| = 16. Gösterim seçimi = hangi sorguyu hızlandıracağın (Solomon 23:08)."
#| fig-width: 11.0
#| fig-height: 6.8
# fig-representations (L9 §5 İMZA): kenar listesi vs komşuluk listesi vs matris.
# Veri MOTORDAN (build_example_graph / degree_sums). networkx YOK — elle koordinat.
_RP_POS = {"a": (0, 2), "b": (1, 2), "c": (0, 1), "d": (1, 1),
"e": (0, 0), "f": (1, 0), "g": (2, 0)}
_RP_VERTS = ["a", "b", "c", "d", "e", "f", "g"]
_RP_EDGES = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"),
("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")]
_RP_R = 0.22
def _rp_badge(ax, x, y, w, text, good):
fc = COL_AMBER_100 if good else COL_WHITE
ec = COL_ACCENT if good else COL_SLATE_400
tcol = COL_AMBER_700 if good else COL_SLATE_500
ax.add_patch(FancyBboxPatch(
(x, y - 0.16), w, 0.32, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=fc, ec=ec, linewidth=1.8, zorder=4))
ax.text(x + 0.12, y, text, ha="left", va="center", fontsize=8.0,
color=tcol, weight="bold", zorder=5)
def _rp_reference(ax, x_off, y_off, scale):
px = {v: (x_off + _RP_POS[v][0] * scale, y_off + _RP_POS[v][1] * scale)
for v in _RP_VERTS}
for u, v in _RP_EDGES:
x0, y0 = px[u]
x1, y1 = px[v]
ax.plot([x0, x1], [y0, y1], color=COL_SLATE_400, linewidth=1.6,
zorder=1, solid_capstyle="round")
for v in _RP_VERTS:
x, y = px[v]
ax.add_patch(Circle((x, y), _RP_R, facecolor=COL_BG, edgecolor=COL_PRIMARY,
linewidth=1.8, zorder=3))
ax.text(x, y, v, ha="center", va="center", fontsize=11,
color=COL_TEXT, weight="bold", zorder=4)
_rp_adj = build_example_graph()
assert _rp_adj["a"] == ["b", "c"] and _rp_adj["c"] == ["a", "d", "e"]
assert _rp_adj["f"] == ["d", "e", "g"] and _rp_adj["g"] == ["f"]
_rp_rec, _ = degree_sums(_rp_adj, directed=False)
_rp_nE = len(_RP_EDGES)
assert _rp_rec == 2 * _rp_nE == 16
fig, ax = plt.subplots(figsize=(11.0, 6.8))
fig.patch.set_facecolor(COL_WHITE)
ref_scale, ref_x0, ref_y0 = 0.78, 4.30, 7.20
_rp_reference(ax, ref_x0, ref_y0, ref_scale)
ax.text(ref_x0 + 1.0 * ref_scale, ref_y0 + 2 * ref_scale + 0.52,
"G = (V, E) · 7 düğüm, 8 kenar (yönsüz)",
ha="center", va="center", fontsize=10, color=COL_PRIMARY,
weight="bold", zorder=5)
p1_x, p2_x, p3_x = 0.0, 4.05, 8.20
panel_top, body_top, badge_y0 = 5.95, 5.05, 1.55
PANEL_W, PANEL_H = 3.55, 6.50
def _rp_frame(x, w, h, recommended, title, subtitle):
fc = COL_AMBER_100 if recommended else COL_WHITE
ec = COL_ACCENT if recommended else COL_SLATE_400
ax.add_patch(FancyBboxPatch(
(x - 0.18, badge_y0 - 1.55), w + 0.36, h,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=fc if recommended else COL_WHITE, ec=ec,
linewidth=2.6 if recommended else 1.4, zorder=0,
alpha=0.35 if recommended else 1.0))
ax.text(x + w * 0.5, panel_top, title, ha="center", va="center",
fontsize=10.5, color=COL_AMBER_700 if recommended else COL_PRIMARY,
weight="bold", zorder=5)
ax.text(x + w * 0.5, panel_top - 0.32, subtitle, ha="center", va="center",
fontsize=8.0, color=COL_SLATE_500, style="italic", zorder=5)
_rp_frame(p1_x, PANEL_W, PANEL_H, False, "1 · Kenar listesi", "kenarların düz listesi")
_rp_frame(p2_x, PANEL_W, PANEL_H, True, "2 · Komşuluk listesi + hash", "ÖNERİLEN gösterim")
_rp_frame(p3_x, PANEL_W, PANEL_H, False, "3 · Komşuluk matrisi", "7×7 ikili ızgara")
# Panel 1 — kenar listesi
list_top, line_h = body_top, 0.42
for k, (u, v) in enumerate(_RP_EDGES):
col, row = k % 2, k // 2
lx = p1_x + 0.20 + col * (PANEL_W * 0.5)
ly = list_top - row * line_h
ax.add_patch(FancyBboxPatch(
(lx, ly - 0.15), PANEL_W * 0.5 - 0.30, 0.30,
boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.2, zorder=3))
ax.text(lx + (PANEL_W * 0.5 - 0.30) * 0.5, ly, f"({u}, {v})",
ha="center", va="center", fontsize=9.0, color=COL_TEXT,
family="monospace", zorder=4)
ax.text(p1_x + PANEL_W * 0.5, list_top - 4 * line_h - 0.30,
"sorgu “a–g var mı?” → TÜM listeyi tara", ha="center", va="center",
fontsize=8.2, color=COL_SLATE_500, zorder=5)
_rp_badge(ax, p1_x + 0.05, badge_y0, PANEL_W - 0.10, "kenar sorgusu O(E) ✗ yavaş", False)
_rp_badge(ax, p1_x + 0.05, badge_y0 - 0.46, PANEL_W - 0.10, "komşu gezme O(E)", False)
_rp_badge(ax, p1_x + 0.05, badge_y0 - 0.92, PANEL_W - 0.10, "yer O(E)", False)
# Panel 2 — komşuluk listesi + hash
adj_top, adj_line_h = body_top, 0.50
for k, v in enumerate(_RP_VERTS):
ly = adj_top - k * adj_line_h
neigh = "{" + ", ".join(_rp_adj[v]) + "}"
ax.add_patch(Circle((p2_x + 0.30, ly), 0.155, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=1.6, zorder=4))
ax.text(p2_x + 0.30, ly, v, ha="center", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(p2_x + 0.58, ly, "→", ha="left", va="center", fontsize=9,
color=COL_SLATE_500, zorder=5)
ax.text(p2_x + 0.92, ly, neigh, ha="left", va="center", fontsize=9.0,
color=COL_TEXT, family="monospace", zorder=5)
_rp_badge(ax, p2_x + 0.05, badge_y0, PANEL_W - 0.10, "kenar sorgusu O(1) beklenen", True)
_rp_badge(ax, p2_x + 0.05, badge_y0 - 0.46, PANEL_W - 0.10, "komşu gezme O(derece)", True)
_rp_badge(ax, p2_x + 0.05, badge_y0 - 0.92, PANEL_W - 0.10, "yer O(V + E)", True)
# Panel 3 — komşuluk matrisi
edge_set = set()
for u, v in _RP_EDGES:
edge_set.add((u, v))
edge_set.add((v, u))
m_cell, m_x0, m_y_top = 0.345, p3_x + 0.55, body_top - 0.05
for j, cv in enumerate(_RP_VERTS):
ax.text(m_x0 + (j + 0.5) * m_cell, m_y_top + 0.18, cv, ha="center",
va="center", fontsize=7.5, color=COL_SLATE_500, weight="bold", zorder=5)
for i, rv in enumerate(_RP_VERTS):
ax.text(m_x0 - 0.15, m_y_top - (i + 0.5) * m_cell, rv, ha="right",
va="center", fontsize=7.5, color=COL_SLATE_500, weight="bold", zorder=5)
for j, cv in enumerate(_RP_VERTS):
cx = m_x0 + j * m_cell
cy = m_y_top - (i + 1) * m_cell
filled = (rv, cv) in edge_set
ax.add_patch(FancyBboxPatch(
(cx, cy), m_cell * 0.92, m_cell * 0.92, boxstyle="square,pad=0.0",
fc=COL_PRIMARY if filled else COL_WHITE,
ec=COL_PRIMARY if filled else COL_SLATE_400, linewidth=1.0, zorder=3))
if filled:
ax.text(cx + m_cell * 0.46, cy + m_cell * 0.46, "1", ha="center",
va="center", fontsize=6.5, color=COL_WHITE, weight="bold", zorder=4)
_rp_badge(ax, p3_x + 0.05, badge_y0, PANEL_W - 0.10, "kenar sorgusu O(1)", True)
_rp_badge(ax, p3_x + 0.05, badge_y0 - 0.46, PANEL_W - 0.10, "komşu gezme O(V) ✗", False)
_rp_badge(ax, p3_x + 0.05, badge_y0 - 0.92, PANEL_W - 0.10, "yer O(V²) ✗", False)
fig.suptitle(
"Aynı çizge, üç gösterim: kenar listesi · komşuluk listesi · komşuluk matrisi",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text((p1_x + p3_x + PANEL_W) * 0.5, badge_y0 - 1.95,
"gösterim seçimi = hangi sorguyu hızlandıracağın — kenar sorgusu mu, "
"komşu gezme mi, bellek mi? (Solomon 23:08)",
ha="center", va="center", fontsize=9.0, color=COL_SLATE_500,
style="italic", zorder=6)
ax.set_xlim(p1_x - 0.5, p3_x + PANEL_W + 0.5)
ax.set_ylim(badge_y0 - 2.45, ref_y0 + 2 * ref_scale + 0.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 6. Yollar ve En Kısa Yol {#sec-6-yollar-ve-en-kisa-yol}
Bir **yol (path)**, ardışık çiftleri kenar olan bir düğüm dizisidir. **Uzunluğu** $=$ kenar sayısı ($=$ düğüm sayısı $-1$; sık yapılan hata: $+1$). **En kısa yol**, iki düğüm arasında en az kenarlı yoldur.
> *"a path is nothing more than a sequence of vertices where every pair of adjacent vertices is an edge."* — Solomon, 27:15
Üç model problem (artan zorlukta): **(1) tek-çift erişilebilirlik** ($s$'den $t$'ye yol var mı?), **(2) tek-çift en kısa yol**, **(3) tek-kaynak en kısa yol (SSSP)** — $s$'den *her* düğüme en kısa mesafe. Bunlar **indirgemeyle** bağlıdır: SSSP çözülürse (2) çözülür (yalnız $t$'ye bak), (2) çözülürse (1) çözülür ($\infty$ ise erişilemez). Bugün (3)'ü çözeriz.
> *"a key idea in an algorithms class is this idea of reduction — that I can use one function to solve another."* — Solomon, 31:12
@fig-three-problems üç problemi soldan sağa artan güçle dizer ve aralarındaki indirgeme oklarını gösterir: en güçlü problem (SSSP) çözülünce daha güçsüz ikisi de "bedava" çözülür.
```{python}
#| label: fig-three-problems
#| fig-cap: "Üç çizge problemi + indirgeme zinciri: SSSP çözünce üçü birden çözülür (L9 §6, İMZA figür). Soldan sağa artan güç: (1) TEK-ÇİFT ERİŞİLEBİLİRLİK — s'den t'ye yol VAR mı? örnek a→g → EVET. (2) TEK-ÇİFT EN KISA YOL — kaç adımda? a→g = 4 adım. (3) SSSP (amber çerçeve, bugün çözülen) — s'den HER düğüme uzaklık: a:0 b:1 c:1 d:2 e:2 f:3 g:4. Kutular arası SOLA dönük amber 'indirger' okları: 3→2 ('yalnız t'ye bak'), 2→1 ('uzaklık sonlu mu?'). İndirgeme = bir problemi, başka bir problemin çözümünü ÇAĞIRAN bir fonksiyonla çözmek. Veri MOTORDAN: bfs(build_example_graph(),'a') → delta[g]=4, tablo a:0 b:1 c:1 d:2 e:2 f:3 g:4; reconstruct_path → a→g yolu VAR (erişilebilir) (Solomon 31:12)."
#| fig-width: 11.0
#| fig-height: 6.4
# fig-three-problems (L9 §6 İMZA): erişilebilirlik ⊂ tek-çift SP ⊂ SSSP + indirgeme.
# Veri MOTORDAN (bfs / build_example_graph / reconstruct_path). networkx YOK.
_TP_POS = {"a": (0, 2), "b": (1, 2), "c": (0, 1), "d": (1, 1),
"e": (0, 0), "f": (1, 0), "g": (2, 0)}
_TP_EDGES = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"),
("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")]
_TP_R = 0.16
def _tp_mini(ax, ox, oy, scale, delta=None, path_nodes=None, source="a", sink="g"):
path_nodes = set(path_nodes or [])
path_edges = set()
if path_nodes:
pl = [n for n in ("a", "b", "d", "f", "g") if n in path_nodes]
for i in range(len(pl) - 1):
path_edges.add(frozenset((pl[i], pl[i + 1])))
def XY(node):
gx, gy = _TP_POS[node]
return ox + gx * scale, oy + gy * scale
for u, v in _TP_EDGES:
x0, y0 = XY(u)
x1, y1 = XY(v)
hot = frozenset((u, v)) in path_edges
ax.plot([x0, x1], [y0, y1], color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.6 if hot else 1.3, zorder=3 if hot else 1,
solid_capstyle="round")
for node in _TP_POS:
x, y = XY(node)
if node == source:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.6, COL_AMBER_700
elif node == sink:
fc, ec, lw, tcol = COL_BG, COL_ACCENT, 2.6, COL_TEXT
elif node in path_nodes:
fc, ec, lw, tcol = COL_AMBER_100, COL_AMBER_600, 1.8, COL_TEXT
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.4, COL_TEXT
ax.add_patch(Circle((x, y), _TP_R * scale, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, node, ha="center", va="center", fontsize=8.5,
color=tcol, weight="bold", zorder=6)
if delta is not None:
ax.text(x + _TP_R * scale + 0.02 * scale, y + _TP_R * scale,
str(delta[node]), ha="left", va="bottom", fontsize=7.5,
color=COL_AMBER_700, weight="bold", zorder=7)
def _tp_box(ax, bx, by, bw, bh, accent):
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_BG, ec=COL_ACCENT if accent else COL_PRIMARY,
linewidth=2.8 if accent else 1.8, zorder=2))
_tp_G = build_example_graph()
_tp_delta, _tp_parent = bfs(_tp_G, "a")
_tp_path = reconstruct_path(_tp_parent, "a", "g")
assert _tp_delta["g"] == 4 and _tp_path[0] == "a" and _tp_path[-1] == "g"
_tp_steps = _tp_delta["g"]
_tp_order = ["a", "b", "c", "d", "e", "f", "g"]
fig, ax = plt.subplots(figsize=(11.0, 6.4))
fig.patch.set_facecolor(COL_WHITE)
bw, bh, gap, by = 3.30, 4.00, 1.30, 0.0
box_x = [0.0, bw + gap, 2 * (bw + gap)]
accents = [False, False, True]
titles = ["(1) TEK-ÇİFT\nERİŞİLEBİLİRLİK", "(2) TEK-ÇİFT\nEN KISA YOL", "(3) SSSP\n(bugün çözülen)"]
questions = ["s'den t'ye YOL VAR MI?", "s'den t'ye KAÇ ADIMDA?", "s'den HER düğüme uzaklık?"]
for k in range(3):
bx = box_x[k]
_tp_box(ax, bx, by, bw, bh, accents[k])
tcol = COL_AMBER_700 if accents[k] else COL_PRIMARY
ax.text(bx + bw * 0.5, by + bh - 0.46, titles[k], ha="center", va="center",
fontsize=11, color=tcol, weight="bold", linespacing=1.15, zorder=6)
ax.text(bx + bw * 0.5, by + bh - 1.30, questions[k], ha="center", va="center",
fontsize=8.8, color=COL_SLATE_500, style="italic", zorder=6)
scale = 0.72
gx_extent = 2 * scale
graph_oy = by + 1.18
bx = box_x[0]
ox = bx + (bw - gx_extent) * 0.5
_tp_mini(ax, ox, graph_oy, scale, path_nodes=_tp_path)
ax.text(bx + bw * 0.5, by + 0.42, "a → g yol VAR → EVET", ha="center",
va="center", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=6)
bx = box_x[1]
ox = bx + (bw - gx_extent) * 0.5
_tp_mini(ax, ox, graph_oy, scale, path_nodes=_tp_path)
ax.text(bx + bw * 0.5, by + 0.42, f"a → g = {_tp_steps} adım", ha="center",
va="center", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=6)
bx = box_x[2]
ox = bx + (bw - gx_extent) * 0.5
_tp_mini(ax, ox, graph_oy + 0.30, scale, delta=_tp_delta)
table = " ".join(f"{v}:{_tp_delta[v]}" for v in _tp_order)
ax.text(bx + bw * 0.5, by + 0.42, table, ha="center", va="center", fontsize=9.0,
color=COL_TEXT, weight="bold", family="monospace", zorder=6)
arrow_y = by + bh + 0.50
for k in (2, 1):
x_from = box_x[k] + bw * 0.18
x_to = box_x[k - 1] + bw * 0.82
ax.add_patch(FancyArrowPatch(
(x_from, arrow_y), (x_to, arrow_y), arrowstyle="-|>", mutation_scale=18,
color=COL_AMBER_700, linewidth=2.4, zorder=4, connectionstyle="arc3,rad=0.32"))
ax.text((x_from + x_to) * 0.5, arrow_y + 0.62, "indirger", ha="center",
va="center", fontsize=9.0, color=COL_AMBER_700, weight="bold",
style="italic", zorder=5)
ax.text((box_x[2] + box_x[1]) * 0.5 + bw * 0.5, arrow_y - 0.46, "yalnız t'ye bak",
ha="center", va="center", fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=5)
ax.text((box_x[1] + box_x[0]) * 0.5 + bw * 0.5, arrow_y - 0.46, "uzaklık sonlu mu?",
ha="center", va="center", fontsize=7.8, color=COL_SLATE_500, style="italic", zorder=5)
py = by - 0.62
ax.add_patch(FancyArrowPatch(
(box_x[0] + 0.10, py), (box_x[2] + bw - 0.10, py), arrowstyle="-|>",
mutation_scale=16, color=COL_SLATE_400, linewidth=1.6, zorder=2))
ax.text((box_x[0] + box_x[2] + bw) * 0.5, py - 0.30,
"artan güç — en güçlü problem (SSSP) en güçsüzü (erişilebilirlik) de çözer",
ha="center", va="center", fontsize=9.0, color=COL_SLATE_500, style="italic", zorder=3)
fig.suptitle(
"Üç çizge problemi + indirgeme zinciri: SSSP çözünce üçü birden çözülür",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text((box_x[0] + box_x[2] + bw) * 0.5, py - 0.74,
"indirgeme = bir problemi, başka bir problemin çözümünü ÇAĞIRAN bir "
"fonksiyonla çözmek (Solomon 31:12)",
ha="center", va="center", fontsize=8.8, color=COL_AMBER_700, weight="bold", zorder=3)
ax.set_xlim(box_x[0] - 0.6, box_x[2] + bw + 0.6)
ax.set_ylim(py - 1.05, arrow_y + 1.05)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 7. En Kısa Yol Ağacı {#sec-7-en-kisa-yol-agaci}
Her düğüme giden tam yolu saklamak $O(V^2)$ yer ister (her yol $O(V)$, $V$ yol). Daha iyisi: her düğümde yalnızca **öncülünü (predecessor)** $P(v)$ tut — en kısa yolda $v$'den bir önceki düğüm. Yolu, $P(v), P(P(v)), \ldots$ ile geriye izleyerek kurarsın. Yer: $O(V)$.
**Çalışılan Örnek — optimal alt yapı.** Bu, en kısa yolların güzel özelliğine dayanır: örnek çizgemizde $a$'dan $g$'ye en kısa yol $a \to b \to d \to f \to g$'dir; onun bir öneki ($a \to b \to d$) de $a$'dan $d$'ye en kısa yoldur. (Aksi halde daha kısa bir $a \leadsto d$ parçasını araya ekleyip $a \to g$ yolunu kısaltırdık — en kısa olmasıyla çelişir.) Bu **optimal alt yapı** sayesinde, tüm yol yerine tek bir "geri ok" yeterlidir. Sonuçta oluşan yapı bir **ağaçtır** (döngü olamaz — geri izleme kaynağa varır).
> *"this object is called the shortest path tree."* — Solomon, 38:31
(Uyarı: tek bir kenar eklemek *her* düğümün en kısa yolunu değiştirebilir; kaynağı değiştirmek de — o zaman her şeyi yeniden hesaplarız.)
@fig-sp-tree örnek çizge üzerinde öncül ağacını çizer: kalın geri oklar her düğümden ebeveynine ($P(v)$), amber yol $a \to g$ geriye izlenir ($g \to f \to d \to b \to a$, ters çevir $\to [a, b, d, f, g]$), sağda öncül tablosu ve "$O(V)$ yer vs üstü çizili $O(V^2)$" karşılaştırması.
```{python}
#| label: fig-sp-tree
#| fig-cap: "En kısa yol ağacı: öncül P(v) ile geriye izleme → yol [a, b, d, f, g] (L9 §7, İMZA figür). Sol/orta: örnek çizge; tüm kenarlar soluk slate; ÖNCÜL kenarları (b→a, c→a, d→b, e→c, f→d, g→f) kalın GERİ OKLARI (çocuktan ebeveyne) → bu oklar en kısa yol AĞACINI kurar. a→g yolu amber vurgu: g→f→d→b→a geriye izle, ters çevir → [a,b,d,f,g]; a→d öneki amber kesikli (optimal alt yapı). Sağ panel: öncül tablosu P (a kök, b:a, c:a, d:b, e:c, f:d, g:f); 'yer O(V)' vs üstü çizili 'tüm yollar O(V²)'. Alt kutu: OPTİMAL ALT YAPI — en kısa yolun her öneki de en kısadır → tek geri ok yeter. Veri MOTORDAN: parent = {a:None, b:a, c:a, d:b, e:c, f:d, g:f}; reconstruct_path(P,a,g) = [a,b,d,f,g] (Solomon 38:31)."
#| fig-width: 10.5
#| fig-height: 6.4
# fig-sp-tree (L9 §7 İMZA): öncül ağacı + geriye izleme + optimal alt yapı.
# Veri MOTORDAN (bfs / reconstruct_path / build_example_graph). networkx YOK.
_ST_POS = {"a": (0.0, 2.0), "b": (1.0, 2.0), "c": (0.0, 1.0), "d": (1.0, 1.0),
"e": (0.0, 0.0), "f": (1.0, 0.0), "g": (2.0, 0.0)}
_ST_EDGES = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"),
("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")]
_ST_R, _ST_XS, _ST_YS = 0.22, 2.05, 1.70
def _st_xy(node):
gx, gy = _ST_POS[node]
return gx * _ST_XS, gy * _ST_YS
def _st_ends(u, v, shrink=_ST_R):
x0, y0 = _st_xy(u)
x1, y1 = _st_xy(v)
dx, dy = x1 - x0, y1 - y0
d = math.hypot(dx, dy)
if d == 0:
return (x0, y0), (x1, y1)
ux, uy = dx / d, dy / d
return (x0 + ux * shrink, y0 + uy * shrink), (x1 - ux * shrink, y1 - uy * shrink)
_st_g = build_example_graph()
_st_src, _st_dst = "a", "g"
_st_delta, _st_parent = bfs(_st_g, _st_src)
_st_path = reconstruct_path(_st_parent, _st_src, _st_dst)
assert _st_path == ["a", "b", "d", "f", "g"]
assert _st_parent == {"a": None, "b": "a", "c": "a", "d": "b",
"e": "c", "f": "d", "g": "f"}
_st_pred = [(v, p) for v, p in _st_parent.items() if p is not None]
_st_pathedge = set()
for i in range(len(_st_path) - 1):
_st_pathedge.add(frozenset((_st_path[i], _st_path[i + 1])))
_st_prefix = _st_path[:3]
_st_prefedge = set()
for i in range(len(_st_prefix) - 1):
_st_prefedge.add(frozenset((_st_prefix[i], _st_prefix[i + 1])))
fig, ax = plt.subplots(figsize=(10.5, 6.4))
fig.patch.set_facecolor(COL_WHITE)
for u, v in _ST_EDGES:
(x0, y0), (x1, y1) = _st_ends(u, v)
ax.plot([x0, x1], [y0, y1], color=COL_SLATE_400, linewidth=1.3,
alpha=0.55, zorder=1, solid_capstyle="round")
for child, par in _st_pred:
(cx, cy), (px, py) = _st_ends(child, par)
e_key = frozenset((child, par))
if e_key in _st_pathedge:
col, lw, z = COL_ACCENT, 3.4, 4
else:
col, lw, z = COL_SLATE_500, 2.4, 3
ax.add_patch(FancyArrowPatch(
(cx, cy), (px, py), arrowstyle="-|>", mutation_scale=15,
color=col, linewidth=lw, zorder=z, shrinkA=0, shrinkB=0))
if e_key in _st_prefedge:
ax.plot([cx, px], [cy, py], color=COL_AMBER_600, linewidth=1.8,
linestyle=(0, (3, 2)), alpha=0.95, zorder=5)
_st_pathnodes = set(_st_path)
for node in _ST_POS:
x, y = _st_xy(node)
if node == _st_src:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 3.2, COL_AMBER_700
elif node == _st_dst:
fc, ec, lw, tcol = COL_ACCENT, COL_AMBER_700, 3.0, COL_WHITE
elif node in _st_pathnodes:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.8, COL_AMBER_700
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.7, COL_TEXT
ax.add_patch(Circle((x, y), _ST_R, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=6))
ax.text(x, y, node, ha="center", va="center", fontsize=13, color=tcol, weight="bold", zorder=7)
_sx, _sy = _st_xy(_st_src)
ax.text(_sx - _ST_R - 0.12, _sy + _ST_R + 0.02, "kaynak s", ha="right", va="bottom",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=8)
_dx, _dy = _st_xy(_st_dst)
ax.text(_dx + _ST_R + 0.10, _dy - _ST_R - 0.04, "hedef", ha="left", va="top",
fontsize=9, color=COL_AMBER_700, weight="bold", zorder=8)
gx_min = min(_st_xy(n)[0] for n in _ST_POS)
gx_max = max(_st_xy(n)[0] for n in _ST_POS)
gy_min = min(_st_xy(n)[1] for n in _ST_POS)
ax.text((gx_min + gx_max) * 0.5, gy_min - 0.62,
"kalın ok = öncül P(v): çocuktan EBEVEYNE (geri) — bu oklar en kısa "
"yol AĞACINI kurar", ha="center", va="center", fontsize=8.6,
color=COL_SLATE_500, style="italic", zorder=8)
ax.text((gx_min + gx_max) * 0.5, gy_min - 0.98,
"amber yol: g → f → d → b → a geriye izle, ters çevir → [a, b, d, f, g]",
ha="center", va="center", fontsize=8.8, color=COL_AMBER_700, weight="bold", zorder=8)
box_x, box_w, row_h = gx_max + 0.95, 3.25, 0.46
nodes_order = ["a", "b", "c", "d", "e", "f", "g"]
box_top = gy_min + 2.0 * _ST_YS + _ST_R
box_h = (len(nodes_order) + 1.7) * row_h
ax.add_patch(FancyBboxPatch(
(box_x, box_top - box_h), box_w, box_h,
boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_BG, ec=COL_ACCENT, linewidth=2.0, zorder=4))
ax.text(box_x + box_w * 0.5, box_top - row_h * 0.62, "öncül tablosu P",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=6)
col_v_x, col_p_x = box_x + box_w * 0.30, box_x + box_w * 0.72
head_y = box_top - row_h * 1.35
ax.text(col_v_x, head_y, "düğüm v", ha="center", va="center", fontsize=8.8,
color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(col_p_x, head_y, "öncül P(v)", ha="center", va="center", fontsize=8.8,
color=COL_PRIMARY, weight="bold", zorder=6)
ax.plot([box_x + 0.18, box_x + box_w - 0.18], [head_y - row_h * 0.42] * 2,
color=COL_SLATE_400, linewidth=1.0, zorder=6)
for r, node in enumerate(nodes_order):
ry = head_y - (r + 1) * row_h
on_path = node in _st_pathnodes
vcol = COL_AMBER_700 if on_path else COL_TEXT
pval = _st_parent[node]
pstr = "— (kök)" if pval is None else pval
ax.text(col_v_x, ry, node, ha="center", va="center", fontsize=10, color=vcol,
weight="bold", zorder=6, family="monospace")
ax.text(col_p_x, ry, pstr, ha="center", va="center", fontsize=10, color=vcol,
weight="bold" if on_path else "normal", zorder=6, family="monospace")
cmp_y = box_top - box_h - 0.40
ax.text(box_x + box_w * 0.5, cmp_y + 0.10, "her düğüm 1 öncül → n−1 kenar",
ha="center", va="center", fontsize=8.8, color=COL_TEXT, zorder=6)
ax.text(box_x + box_w * 0.30, cmp_y - 0.32, "yer O(V)", ha="center", va="center",
fontsize=11.5, color=COL_AMBER_700, weight="bold", zorder=6)
bad_x = box_x + box_w * 0.74
ax.text(bad_x, cmp_y - 0.32, "tüm yollar O(V²)", ha="center", va="center",
fontsize=9.2, color=COL_SLATE_500, zorder=6)
ax.plot([bad_x - 0.62, bad_x + 0.62], [cmp_y - 0.32] * 2, color=COL_AMBER_700,
linewidth=1.8, zorder=7)
full_left = gx_min - 0.55
full_right = box_x + box_w + 0.10
full_w = full_right - full_left
sub_y, sub_h = gy_min - 1.95, 0.94
ax.add_patch(FancyBboxPatch(
(full_left, sub_y - sub_h), full_w, sub_h,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.4, zorder=2))
ax.text(full_left + full_w * 0.5, sub_y - 0.30,
"OPTİMAL ALT YAPI — en kısa yolun her ÖNEKİ de en kısa yoldur",
ha="center", va="center", fontsize=10.2, color=COL_AMBER_700, weight="bold", zorder=4)
ax.text(full_left + full_w * 0.5, sub_y - 0.66,
"a→d öneki (amber kesikli) zaten en kısa → her düğüm için TEK geri ok "
"(öncül) yeterli; yolları ayrı saklamaya gerek yok",
ha="center", va="center", fontsize=8.8, color=COL_TEXT, style="italic", zorder=4)
fig.suptitle(
"En kısa yol ağacı: öncül P(v) ile geriye izleme → yol [a, b, d, f, g]",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text((gx_min + gx_max) * 0.5, gy_min + 2.0 * _ST_YS + 0.62,
"BFS kaynaktan (s = a) her düğüme bir öncül atar — bu öncüller bir "
"AĞAÇ kurar (komşuluk listesi, yönsüz çizge)",
ha="center", va="center", fontsize=9.0, color=COL_SLATE_500, style="italic", zorder=8)
ax.text(full_left + full_w * 0.5, sub_y - sub_h - 0.34,
"reconstruct_path(P, s, t): t'den öncülleri geriye izle, ters çevir · "
"O(yol uzunluğu) · (Solomon 38:31 shortest path tree)",
ha="center", va="center", fontsize=8.4, color=COL_SLATE_500, style="italic", zorder=8)
ax.set_xlim(full_left - 0.30, full_right + 0.35)
ax.set_ylim(sub_y - sub_h - 0.70, gy_min + 2.0 * _ST_YS + 0.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 8. Seviye Kümeleri ve BFS {#sec-8-seviye-kumeleri-ve-bfs}
**Seviye kümesi** $L_k$: kaynaktan tam $k$ uzaklıktaki düğümler. $L_0 = \{\text{kaynak}\}$. BFS, bu kümeleri **katman katman** üretir.
> *"the level set... all the vertices that are distance k away from my source."* — Solomon, 42:08
**Çalışılan Örnek — BFS algoritması.** Başlat: $L_0 = \{s\}$, $\delta(s, s) = 0$, $P$ boş. Sonra, önceki seviye boş olmayana dek ($i = 1, 2, \ldots$): önceki seviyedeki her $u$ için, $u$'nun **henüz görülmemiş** her komşusu $v$'ye: $v$'yi $L_i$'ye ekle, $\delta(s, v) = i$ yap, $P(v) = u$ ata. "Henüz görülmemiş" şart — bir düğümü iki seviyeye koymayız (ilk görüldüğü uzaklık en kısadır).
> *"Breadth-First search... an algorithm for computing all of those level sets."* — Solomon, 43:35
Mantık tümevarımsaldır: $u$'ya $i-1$ adımda ulaşılıyorsa, komşusuna $i$ adımda ulaşılır. Algoritma $\delta$ (mesafe), $P$ (öncül) ve $L$ (seviye) bilgilerini tek seferde doldurur.
@fig-bfs-levels örnek çizgede seviye kümelerini "dalga dalga" gösterir: kaynak $a$'dan eş-merkezli halkalar, her düğüm bulunduğu seviyenin tonuyla, altında $\delta$ rozeti.
```{python}
#| label: fig-bfs-levels
#| fig-cap: "BFS = dalga dalga yayılma: seviye kümeleri Lₖ (kaynaktan tam k uzaklık) (L9 §8, İMZA figür). Örnek çizge (7 düğüm, 8 yönsüz kenar) kaynak a'dan eş-merkezli KESİKLİ dalga yaylarıyla — bir taşın suya düşmesiyle oluşan halkalar gibi. Her düğüm bulunduğu seviyenin tonuyla dolar: L0 a amber dolgu (kaynak), L1 b,c amber-300, L2 d,e amber-100, L3 f slate açık, L4 g beyaz+slate çerçeve. Her düğümün altında δ rozeti: a:0 b:1 c:1 d:2 e:2 f:3 g:4. Sağda seviye tablosu L0={a} L1={b,c} L2={d,e} L3={f} L4={g}. Bir düğüm İLK görüldüğü seviyede sabitlenir (en kısa uzaklık δ) — iki seviyeye KONMAZ. Veri MOTORDAN: bfs_levels(build_example_graph(),'a') = [[a],[b,c],[d,e],[f],[g]] (Solomon 42:08)."
#| fig-width: 10.5
#| fig-height: 6.5
# fig-bfs-levels (L9 §8 İMZA): seviye kümeleri dalga halkaları + δ rozetleri.
# Veri MOTORDAN (build_example_graph / bfs_levels / bfs). networkx YOK.
_BL_POS = {"a": (0.0, 2.0), "b": (1.0, 2.0), "c": (0.0, 1.0), "d": (1.0, 1.0),
"e": (0.0, 0.0), "f": (1.0, 0.0), "g": (2.0, 0.0)}
_BL_EDGES = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"),
("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")]
_BL_R = 0.22
_BL_STYLE = [
(COL_ACCENT, COL_AMBER_700, COL_WHITE), # L0: amber dolgu (kaynak)
(COL_AMBER_300, COL_AMBER_600, COL_TEXT), # L1
(COL_AMBER_100, COL_ACCENT, COL_TEXT), # L2
(COL_BG, COL_SLATE_500, COL_TEXT), # L3
(COL_WHITE, COL_SLATE_400, COL_TEXT), # L4
]
_bl_g = build_example_graph()
_bl_src = "a"
_bl_levels = bfs_levels(_bl_g, _bl_src)
_bl_delta, _ = bfs(_bl_g, _bl_src)
assert _bl_levels == [["a"], ["b", "c"], ["d", "e"], ["f"], ["g"]]
assert _bl_delta == {"a": 0, "b": 1, "c": 1, "d": 2, "e": 2, "f": 3, "g": 4}
_bl_levelof = {v: k for k, lvl in enumerate(_bl_levels) for v in lvl}
fig, ax = plt.subplots(figsize=(10.5, 6.5))
fig.patch.set_facecolor(COL_WHITE)
sx, sy = _BL_POS[_bl_src]
for k in range(1, len(_bl_levels)):
rr = max(math.hypot(_BL_POS[v][0] - sx, _BL_POS[v][1] - sy) for v in _bl_levels[k])
rr += _BL_R + 0.10
ax.add_patch(Arc((sx, sy), 2 * rr, 2 * rr, theta1=-78, theta2=18,
edgecolor=COL_AMBER_600, linewidth=1.3,
linestyle=(0, (3, 3)), alpha=0.55, zorder=0))
ang = math.radians(-30)
lx = sx + rr * math.cos(ang)
ly = sy + rr * math.sin(ang)
ax.text(lx + 0.10, ly - 0.04, f"L{k}", ha="left", va="center", fontsize=8.5,
color=COL_AMBER_700, weight="bold", alpha=0.85, zorder=1)
for u, v in _BL_EDGES:
x0, y0 = _BL_POS[u]
x1, y1 = _BL_POS[v]
ax.plot([x0, x1], [y0, y1], color=COL_SLATE_400, linewidth=1.6,
zorder=2, solid_capstyle="round")
for v, (x, y) in _BL_POS.items():
k = _bl_levelof[v]
fc, ec, tcol = _BL_STYLE[k]
lw = 3.0 if v == _bl_src else 2.2
ax.add_patch(Circle((x, y), _BL_R, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=5))
ax.text(x, y, v, ha="center", va="center", fontsize=13, color=tcol, weight="bold", zorder=6)
ax.text(x, y - _BL_R - 0.17, f"δ={_bl_delta[v]}", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(sx - _BL_R - 0.14, sy + _BL_R + 0.10, "kaynak", ha="right", va="bottom",
fontsize=9, color=COL_AMBER_700, weight="bold", style="italic", zorder=6)
tbl_x, tbl_top, row_h = 2.95, 2.30, 0.52
ax.text(tbl_x, tbl_top + 0.42, "seviye kümeleri Lₖ", ha="left", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=6)
for k, lvl in enumerate(_bl_levels):
ry = tbl_top - k * row_h
fc, ec, _tc = _BL_STYLE[k]
ax.add_patch(FancyBboxPatch(
(tbl_x, ry - 0.14), 0.30, 0.30, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=fc, ec=ec, linewidth=1.8, zorder=4))
members = ", ".join(lvl)
ax.text(tbl_x + 0.46, ry, f"L{k} = {{{members}}}", ha="left", va="center",
fontsize=10, color=COL_TEXT, family="monospace", zorder=5)
fig.suptitle(
"BFS = dalga dalga yayılma: seviye kümeleri Lₖ (kaynaktan tam k uzaklık)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(0.5, 2.78,
"kaynak a'dan eş-merkezli halkalar — Lₖ kaynaktan tam k uzaklıktaki düğümler",
ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic", zorder=6)
ax.text(0.5, -0.92,
"bir düğüm İLK görüldüğü seviyede sabitlenir (en kısa uzaklık δ) — "
"iki seviyeye KONMAZ · BFS tek geçişte δ/L: O(V+E) · (Solomon 42:08)",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6)
ax.set_xlim(-1.0, tbl_x + 3.0)
ax.set_ylim(-1.25, 3.05)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
BFS'i komşuluk listesi üzerinde Python'da yazmak kısadır (kuyruk = FIFO; "henüz görülmemiş" kontrolü $\delta$ sözlüğünde):
```python
from collections import deque
def bfs(adj, s):
delta = {s: 0}
parent = {s: None}
queue = deque([s])
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in delta: # henuz gorulmemis
delta[v] = delta[u] + 1
parent[v] = u
queue.append(v)
return delta, parent
```
## 9. BFS Çalışma Süresi O(V + E) {#sec-9-bfs-calisma-suresi}
İki bileşen: (1) $V$ boyutlu mesafe/öncül dizilerini ayırmak $O(V)$; (2) "her düğüm için her komşusunu gez" döngüsü — her düğüm tam bir kez görülür (seviye sırasında), komşu gezmelerinin toplamı $=$ derecelerin toplamı $= O(E)$. Toplam:
$$T(\text{BFS}) = O(V + E)$$
> *"our algorithm takes big O of mod v plus mod e time."* — Solomon, 51:40
Bu sınıfta buna **doğrusal zaman** denir (çizgeyi saklamak için kullanılan yerde doğrusal). İki terim de gereklidir: kenarsız çizgede $V$ baskın; kenar arttıkça $E$ ($V^2$'ye kadar) baskın — $V^2$ demekten daha bilgilendirici bir ifade.
@fig-bfs-run bu yürütmeyi adım adım izler: kuyruk (FIFO) katman katman boşalır, $\delta$ tablosu tek geçişte soldan sağa dolar; toplam-iş kutusu $\sum \deg = 2|E| = 16$ ile $O(V + E)$ sonucunu özetler.
```{python}
#| label: fig-bfs-run
#| fig-cap: "BFS yürütme izi: kuyruk katman katman boşalır, δ tablosu tek geçişte dolar (L9 §8-9, İMZA figür). Sol üst: örnek çizge (7 düğüm, 8 yönsüz kenar) + her düğümün δ değeri. Sağ: 7 satırlık adım izi (her satır = bir adım). Her düğüm KUYRUKTAN tam BİR kez çıkar (işlenir, amber dolu daire); çıkışta HENÜZ GÖRÜLMEMİŞ komşulara δ[v]=δ[u]+1 yazılır (amber-100 daireler) ve kuyruk SONUNA eklenir. Adımlar: 1.a→ekle b,c | 2.b→ekle d | 3.c→ekle e | 4.d→ekle f | 5.e→(yok, tümü görülmüş) | 6.f→ekle g | 7.g→(yok). Sağ alt kutu: her düğüm 1 kez işlenir → O(V); komşu gezmeleri = derece toplamı Σ deg = 2|E| = 16 → O(E); ⇒ BFS = O(V+E) (V=7, E=8). Doğrusal zaman = çizgeyi saklama YERİNDE doğrusal. Veri MOTORDAN: bfs_trace 7 adım, adım1 u=a added=[b,c], son delta a:0 b:1 c:1 d:2 e:2 f:3 g:4 (Solomon 51:40)."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-bfs-run (L9 §8-9 İMZA): BFS adım-izi (kuyruk + δ tablosu) + toplam-iş O(V+E).
# Veri MOTORDAN (bfs_trace / bfs / degree_sums / build_example_graph). networkx YOK.
_BR_POS = {"a": (0, 2), "b": (1, 2), "c": (0, 1), "d": (1, 1),
"e": (0, 0), "f": (1, 0), "g": (2, 0)}
_BR_EDGES = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"),
("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")]
_BR_ORDER = ["a", "b", "c", "d", "e", "f", "g"]
_BR_GR, _BR_ADD_R = 0.26, 0.20
_BR_QC_W, _BR_QC_H = 0.40, 0.40
_BR_DC_W, _BR_DC_H = 0.40, 0.46
def _br_graph(ax, ox, oy, scale, delta, source):
def P(node):
gx, gy = _BR_POS[node]
return ox + gx * scale, oy + gy * scale
for u, v in _BR_EDGES:
ux, uy = P(u)
vx, vy = P(v)
ax.plot([ux, vx], [uy, vy], color=COL_PRIMARY, linewidth=2.2,
solid_capstyle="round", zorder=1, clip_on=False)
for node in _BR_ORDER:
x, y = P(node)
is_src = (node == source)
ax.add_patch(Circle((x, y), _BR_GR,
facecolor=COL_AMBER_100 if is_src else COL_BG,
edgecolor=COL_ACCENT if is_src else COL_PRIMARY,
linewidth=3.0 if is_src else 1.8, zorder=4, clip_on=False))
ax.text(x, y, node, ha="center", va="center", fontsize=11,
color=COL_AMBER_700 if is_src else COL_TEXT, weight="bold", zorder=5)
ax.text(x + _BR_GR + 0.05, y + _BR_GR - 0.02, f"δ={delta[node]}",
ha="left", va="bottom", fontsize=7.5, color=COL_AMBER_700,
weight="bold", zorder=6)
sx, sy = P(source)
ax.text(sx - _BR_GR - 0.10, sy, "kaynak", ha="right", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(ox + 1.0 * scale, oy + 2 * scale + _BR_GR + 0.40,
"örnek çizge (yönsüz, 7 düğüm · 8 kenar)", ha="center", va="center",
fontsize=9.5, color=COL_PRIMARY, weight="bold", zorder=6)
def _br_small(ax, x, y, label, kind):
if kind == "process":
fc, ec, tcol, lw = COL_ACCENT, COL_AMBER_700, COL_WHITE, 2.2
else:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.2
ax.add_patch(Circle((x, y), _BR_ADD_R, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=6))
ax.text(x, y, label, ha="center", va="center", fontsize=9.5, color=tcol, weight="bold", zorder=7)
def _br_queue(ax, x0, y, items):
if not items:
ax.text(x0 + _BR_QC_W * 0.5, y + _BR_QC_H * 0.5, "∅", ha="center",
va="center", fontsize=11, color=COL_SLATE_400, zorder=5)
return
for k, it in enumerate(items):
x = x0 + k * _BR_QC_W
ax.add_patch(FancyBboxPatch(
(x, y), _BR_QC_W * 0.88, _BR_QC_H, boxstyle="square,pad=0.0",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.4, zorder=3))
ax.text(x + _BR_QC_W * 0.44, y + _BR_QC_H * 0.5, str(it), ha="center",
va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5)
def _br_delta(ax, x0, y, delta_now):
for k, node in enumerate(_BR_ORDER):
x = x0 + k * _BR_DC_W
filled = node in delta_now
if filled:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.0, COL_AMBER_700
else:
fc, ec, lw, tcol = COL_WHITE, COL_SLATE_400, 1.0, COL_SLATE_400
ax.add_patch(FancyBboxPatch(
(x, y), _BR_DC_W * 0.88, _BR_DC_H, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=3))
ax.text(x + _BR_DC_W * 0.44, y + _BR_DC_H * 0.5,
str(delta_now[node]) if filled else "·", ha="center", va="center",
fontsize=9.5, color=tcol, weight="bold" if filled else "normal", zorder=5)
_br_adj = build_example_graph()
_br_source = "a"
_br_tr = bfs_trace(_br_adj, _br_source)
_br_steps = _br_tr["steps"]
_br_final = _br_tr["delta"]
_br_dbfs, _ = bfs(_br_adj, _br_source)
assert _br_dbfs == _br_final and len(_br_steps) == 7
assert _br_steps[0]["u"] == "a" and _br_steps[0]["added"] == ["b", "c"]
assert _br_final == {"a": 0, "b": 1, "c": 1, "d": 2, "e": 2, "f": 3, "g": 4}
_br_V = len(_br_adj)
_br_degtotal, _ = degree_sums(_br_adj, directed=False)
_br_E = _br_degtotal // 2
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
col_u, col_add_x0, col_q_x0, col_d_x0 = 5.30, 6.05, 8.15, 10.55
row_top, row_gap = 4.55, 0.74
n_rows = len(_br_steps)
_br_graph(ax, ox=0.35, oy=1.55, scale=1.55, delta=_br_final, source=_br_source)
y_head = row_top + 0.62
ax.text(col_u, y_head, "işlenen u", ha="center", va="center", fontsize=9,
color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(col_add_x0 + 0.55, y_head, "eklenenler (δ=δ[u]+1)", ha="center", va="center",
fontsize=9, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(col_q_x0 + 0.9, y_head, "kuyruk (ön → arka)", ha="center", va="center",
fontsize=9, color=COL_PRIMARY, weight="bold", zorder=6)
ax.text(col_d_x0 + len(_BR_ORDER) * _BR_DC_W * 0.5 - _BR_DC_W * 0.06, y_head,
"δ tablosu", ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=6)
for k, node in enumerate(_BR_ORDER):
x = col_d_x0 + k * _BR_DC_W + _BR_DC_W * 0.44
ax.text(x, y_head - 0.30, node, ha="center", va="center", fontsize=7.5,
color=COL_SLATE_500, weight="bold", zorder=6)
for r, st in enumerate(_br_steps):
y = row_top - r * row_gap
u, added, queue, delta_now = st["u"], st["added"], st["queue"], st["delta"]
ax.text(col_u - 0.78, y, f"{r + 1}.", ha="right", va="center", fontsize=8.5,
color=COL_SLATE_500, weight="bold", zorder=6)
_br_small(ax, col_u, y, u, "process")
if added:
for k, v in enumerate(added):
ax_x = col_add_x0 + k * 0.62
_br_small(ax, ax_x, y, v, "add")
ax.text(ax_x, y - _BR_ADD_R - 0.10, f"δ={delta_now[v]}", ha="center",
va="top", fontsize=6.8, color=COL_AMBER_700, weight="bold", zorder=7)
else:
ax.text(col_add_x0 + 0.20, y, "(yok — tümü görülmüş)", ha="left", va="center",
fontsize=7.5, color=COL_SLATE_400, style="italic", zorder=6)
_br_queue(ax, col_q_x0, y - _BR_QC_H * 0.5, queue)
_br_delta(ax, col_d_x0, y - _BR_DC_H * 0.5, delta_now)
if r < n_rows - 1:
ax.plot([col_u - 1.05, col_d_x0 + len(_BR_ORDER) * _BR_DC_W],
[y - row_gap * 0.5, y - row_gap * 0.5],
color=COL_SLATE_400, linewidth=0.5, alpha=0.35, zorder=0)
box_x = col_u - 1.05
box_w = (col_d_x0 + len(_BR_ORDER) * _BR_DC_W) - box_x
box_top = row_top - (n_rows - 1) * row_gap - _BR_QC_H * 0.5 - 0.30
box_h = 1.18
ax.add_patch(FancyBboxPatch(
(box_x, box_top - box_h), box_w, box_h,
boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_BG, ec=COL_ACCENT, linewidth=2.0, zorder=3))
ax.text(box_x + 0.22, box_top - 0.32,
"TOPLAM İŞ — her düğüm KUYRUKTAN tam 1 kez çıkar → Σ işleme = O(V)",
ha="left", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(box_x + 0.22, box_top - 0.64,
f"çıkışta komşu gezmeleri = derece toplamı Σ deg = 2|E| = {_br_degtotal} → O(E)",
ha="left", va="center", fontsize=9, color=COL_TEXT, zorder=5)
ax.text(box_x + 0.22, box_top - 0.96,
f"⇒ BFS = O(V + E) (V = {_br_V}, E = {_br_E})",
ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=5)
fig.suptitle(
"BFS yürütme izi: kuyruk katman katman boşalır, δ tablosu tek geçişte dolar",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text(box_x + box_w * 0.5, box_top - box_h - 0.42,
"doğrusal zaman O(V + E) = çizgeyi saklama YERİNDE doğrusal · "
"her düğüm 1 kez işlenir · komşuluk listesi → toplam komşu ziyareti Σ deg "
"(Solomon 51:40)",
ha="center", va="center", fontsize=8.3, color=COL_SLATE_500, style="italic", zorder=6)
ax.set_xlim(box_x - 0.5, col_d_x0 + len(_BR_ORDER) * _BR_DC_W + 0.5)
ax.set_ylim(box_top - box_h - 0.85, row_top + 1.05)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d13}
1. **Çizge** $G = (V, E)$; kenar = düğüm çifti; **yönlü** (sıralı) veya **yönsüz** (sırasız).
2. **Basit çizge**: özdöngüsüz, çoklu-kenarsız; $|E| = O(V^2)$; seyrek/yoğun ayrımı.
3. **Derece toplamı** $= 2|E|$ (yönsüz) / $|E|$ (yönlü) → "her düğüm-her komşu" döngüsü $O(E)$.
4. **Gösterim**: kenar listesi ($O(E)$ sorgu), **komşuluk listesi + hash** ($O(1)$ sorgu), komşuluk matrisi ($O(1)$ sorgu, $O(V)$ komşu).
5. **Yol** = ardışık-kenarlı düğüm dizisi; uzunluk = kenar sayısı; 3 problem indirgemeyle bağlı.
6. **En kısa yol ağacı**: öncül $P(v)$ ile $O(V)$ yer; optimal alt yapı.
7. **BFS**: seviye kümeleri $L_k$; $\delta/P/L$'yi doldurur; $O(V + E)$ (doğrusal).
::: {.callout-important title="Tek Bir Cümle"}
BFS, kaynaktan dışa doğru "dalga dalga" yayılarak (seviye kümeleri) ağırlıksız en kısa yolu $O(V + E)$'de bulur; öncül ağacı sayesinde yolları da $O(V)$ yerde saklar.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d13}
::: {.callout-note collapse="true" title="Soru 1: Aynı çizge için komşuluk listesi mi yoksa komşuluk matrisi mi tercih edilir? Neye bağlı?"}
**Cevap:**
Bağlıdır. **Komşuluk matrisi** kenar sorgusunu ($v \to w$ var mı?) $O(1)$ yapar ama $O(V^2)$ yer ister ve bir düğümün komşularını gezmek $O(V)$'dir (tüm satırı taramak gerekir). **Komşuluk listesi (+ hash)** hem kenar sorgusunu beklenen $O(1)$ hem de komşu gezmeyi $O(\text{derece})$ yapar ve yalnızca $O(V + E)$ yer kullanır. Seyrek çizgelerde ($E \ll V^2$) — ki çoğu gerçek çizge seyrektir — komşuluk listesi belirgin biçimde üstündür.
:::
::: {.callout-note collapse="true" title="Soru 2: En kısa yol ağacı neden tüm yolları saklamaktan (O(V²)) daha az yer (O(V)) kullanır?"}
**Cevap:**
Her düğüm için tam yolu ($V$'ye kadar düğüm) saklarsak $O(V^2)$ olur. Ama optimal alt yapı sayesinde, her düğümde yalnızca **öncülü** $P(v)$ (tek düğüm) tutmak yeterlidir — yolu $P(v), P(P(v)), \ldots$ ile geriye izleyerek yeniden kurarız. Her düğüm bir öncül tuttuğundan toplam $O(V)$ yerdir; yine de her yolu tam olarak verir.
:::
::: {.callout-note collapse="true" title="Soru 3: BFS'te bir düğüm neden yalnızca “henüz görülmemişse” eklenir? Görülmüşse ne olurdu?"}
**Cevap:**
BFS, düğümleri kaynaktan *artan uzaklık* sırasında işler. Bir düğüm ilk kez $L_i$'de görüldüğünde, ona en kısa mesafe tam $i$'dir (daha erken bir seviyede görülmediğine göre). Onu daha sonraki bir $L_j$'ye ($j > i$) tekrar eklersek, yanlış (daha uzun) mesafe atamış oluruz. "Henüz görülmemiş" kontrolü, her düğümün *ilk* (= en kısa) uzaklığını sabitler ve algoritmanın doğruluğunu sağlar.
:::
::: {.callout-note collapse="true" title="Soru 4: BFS neden O(V + E)'dir, neden tek bir terim (örneğin O(V²)) değil?"}
**Cevap:**
İki ayrı maliyet vardır: $V$ boyutlu mesafe/öncül dizilerini ayırmak $O(V)$; ve "her düğüm için her komşusunu gez" döngüsü, derecelerin toplamı $= O(E)$. Her düğüm tam bir kez işlendiğinden çift sayım yoktur. $O(V + E)$ yazmak $O(V^2)$'den daha bilgilendiricidir: kenarsız çizgede $V$ baskın, yoğun çizgede $E$ ($\le V^2$) baskın olur. Tek terim, çizgenin seyrekliğini gizlerdi.
:::
## Egzersizler {#sec-egzersizler-d13}
**Egzersiz 1.** Verilen bir yönlü çizge için $\text{Adj}^{+}$ ve $\text{Adj}^{-}$ kümelerini, her düğümün in/out derecesini yaz; derecelerin toplamının $|E|$ (çıkış) olduğunu doğrula.
**Egzersiz 2.** Bir çizgeyi hem komşuluk listesi hem komşuluk matrisi olarak temsil et; "$v \to w$ var mı?" ve "$u$'nun komşuları" sorgularının her birinde maliyetini karşılaştır.
**Egzersiz 3.** Optimal alt yapıyı kanıtla: $a \to \ldots \to v$ en kısa yol ise, onun her öneki de bir en kısa yoldur. (İpucu: daha kısa bir önek olsaydı ana yolu kısaltırdın.)
**Egzersiz 4.** Python'da komşuluk listesi üzerinde BFS yaz ($\delta$ ve $P$ döndür):
```python
from collections import deque
def bfs(adj, s):
delta = {s: 0}
parent = {s: None}
queue = deque([s])
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in delta: # henuz gorulmemis
delta[v] = delta[u] + 1
parent[v] = u
queue.append(v)
return delta, parent
```
**Egzersiz 5.** BFS'in ürettiği `parent` (öncül) sözlüğünden, $s$'den belirli bir $t$'ye en kısa yolu (düğüm dizisi) yeniden kuran bir fonksiyon yaz. Süresi nedir?
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d13}
**Ders 15 (L10): Derinlemesine Arama (DFS) ve Topolojik Sıralama**
Justin Solomon ile, BFS'in kardeşi **DFS (depth-first search)**'e geçiyoruz: çizgeyi "olabildiğince derine in, sonra geri çekil" mantığıyla gez. DFS, **topolojik sıralama** (bağımlılık sıralaması) ve **çevrim tespiti** için kullanılır. (Not: kitap düzeninde önce **Ders 14 (Quiz 1 Gözden Geçirme, Jason Ku)** araya girer; DFS bunun ardından gelir.)
::: {.callout-warning title="Ders 15 Öncesi Yapılacak"}
- Bu dersin egzersizlerini, özellikle **Egzersiz 4**'ü (BFS) çöz.
- Üç çizge problemini (erişilebilirlik, tek-çift, tek-kaynak) ve indirgemeleri ezberden anlat.
- Ana cümleyi tekrar oku: *"BFS dalga dalga yayılarak ağırlıksız en kısa yolu $O(V + E)$'de bulur."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d13}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **Çizge $G = (V, E)$** | Düğümler + kenarlar; yönlü (sıralı) / yönsüz (sırasız) | Böl. 1 |
| **Basit çizge** | Özdöngüsüz, çoklu-kenarsız; $\lvert E \rvert = O(V^2)$ | Böl. 3 |
| **Derece toplamı** | $2\lvert E \rvert$ (yönsüz) / $\lvert E \rvert$ (yönlü) → komşu döngüsü $O(E)$ | Böl. 4 |
| **Komşuluk listesi** | Düğüm → komşular (hash); kenar sorgusu $O(1)$ | Böl. 5 |
| **Yol / en kısa yol** | Ardışık-kenarlı dizi; uzunluk = kenar sayısı | Böl. 6 |
| **En kısa yol ağacı** | Öncül $P(v)$; $O(V)$ yer; optimal alt yapı | Böl. 7 |
| **Seviye kümesi $L_k$** | Kaynaktan $k$ uzaklıktaki düğümler | Böl. 8 |
| **BFS** | Katman katman; $\delta/P/L$ doldurur; $O(V + E)$ | Böl. 8-9 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d13}
::: {.callout-tip title="6 köprü"}
Bu ders, "bağlı her şeyin evrensel soyutlaması (çizge)" ve "katman katman keşif (BFS)" sezgisini kurar — köprülerin özeti:
1. **Çizge gösterimi** → her sistem tasarımı: sosyal graf, bağımlılık grafı, ağ topolojisi — komşuluk listesi varsayılan.
2. **BFS** → en kısa yol (ağırlıksız), web crawler (katman katman), ağ yayını, "kaç adım uzakta" (LinkedIn derece).
3. **Reduction** → OMSCS CS 6515: problemleri birbirine indirgemek, NP-tamlık dahil her yerde temel teknik.
4. **Optimal alt yapı** → dinamik programlama (DP) köprüsü: en kısa yol, DP'nin habercisidir (alt-problem çözümleri birleşir).
5. **$O(V + E)$ doğrusal** → seyreklik bilinci: gerçek çizgeler seyrektir; $E$-bağlı algoritma $V^2$-bağlıdan çok hızlıdır.
6. **Öncül ağacı** → yol yeniden kurma: routing tablosu, git geçmişi, bağımlılık çözümü — hep "geri izleme".
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Çizge, "bağlı her şeyin" evrensel soyutlamasıdır; onu komşuluk listesiyle saklayıp BFS ile kaynaktan dışa dalga dalga gezersek, ağırlıksız en kısa yolu $O(V + E)$'de buluruz. Ve tüm yolları saklamak yerine sadece "öncül"leri tutarak, $O(V)$ yerde her yolu yeniden kurabiliriz.
:::
