16 Derinlemesine Arama (DFS)

DFS = özyinelemeli derine in, geri çekil; erişilebilirlik O(E) (ebeveyn ağacı, en kısa değil); full DFS → bağlı bileşenler O(V+E); DAG’da ters bitiş sırası = topolojik sıra (u→v ⇒ f(u)<f(v), benzersiz değil); geri kenar (v → atası) = çevrim; bağımlılık çözen her sistem (make/npm/pip) içten içe bunu çalıştırır

Bölüm bilgisi

Solomon’un videosu: YouTube — Lecture 10: Depth-First Search (≈52 dk)
OCW sayfası: MIT 6.006 Lecture 10: Depth-First Search
Seri: MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 15 (L10)
Hoca: Justin Solomon (Demaine/Ku değil)
Okuma süresi: ≈25 dk

Bir önceki ders BFS’i (enine arama) verdi; bu ders onun kardeşi DFS’i çözer ve üç güçlü uygulamayı açar: erişilebilirlik, bağlı bileşenler, topolojik sıralama (+ çevrim tespiti).

16.1 Bu Derste Ne Var?

Ders 13 (L9) BFS’i (enine arama) verdi; Ders 14 (Quiz 1 Gözden Geçirme, Jason Ku) araya girdi. Bugün yine Justin Solomon ile BFS’in kardeşi DFS (depth-first search, derinlemesine arama) ile devam ediyoruz. DFS, çizgeyi “olabildiğince derine in, sonra geri çekil” mantığıyla gezer ve üç güçlü uygulamayı açar: erişilebilirlik, bağlı bileşenler, topolojik sıralama (+ çevrim tespiti).

“in breadth-first search, we’re like, drawing concentric circles. In depth-first search… we’re like, shooting outward until we reach the outer boundary.” — Solomon, 6:55

Üç ana fikir bu derste yan yana gelir:

DFS = özyinelemeli gezinme — bir düğümden komşularına in, her komşu kendi komşularına insin; erişilebilirliği $O(E)$’de çöz.
Bağlı bileşenler — full DFS (her düğüm üzerinde döngü) ile $O(V + E)$’de tüm “kümeleri” bul.
Topolojik sıralama — bir DAG’da, DFS bitiş sırasının tersi geçerli bir bağımlılık sıralaması verir; aynı teknik çevrim tespiti yapar.

flowchart TD
    A["Ders 15 (L10): Derinlemesine Arama (DFS)"] --> D["DFS özyinelemeli iskelet<br/>derine in, geri çekil"]
    D --> D1["ziyaretsiz komşuya in<br/>dibe vur, geri çekil (yığın boşalır)"]
    A --> R["erişilebilirlik O(E)<br/>ebeveyn ağacı P(v)"]
    R --> R1["kaynaktan bir yol — en KISA değil<br/>yalnız erişilebilir kenarlara dokunur"]
    A --> C["bağlı bileşenler<br/>full DFS"]
    C --> C1["tüm düğümler üzerinde döngü<br/>her ada bir DFS ağacı, O(V+E)"]
    A --> T["DAG + topolojik sıra<br/>ters bitiş sırası"]
    T --> T1["u→v ⇒ f(u)&lt;f(v)<br/>benzersiz değil"]
    A --> Y["çevrim tespiti<br/>geri kenar"]
    Y --> Y1["v'den atasına kenar = çevrim<br/>topolojik sıra var ancak ve ancak DAG"]

    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 D,R,C,T,Y branch
    class D1,R1,C1,T1,Y1 leaf

Şekil 16.1: Ders 15’in (L10) kavram haritası: kök = derinlemesine arama (DFS). Beş dal — (1) DFS özyinelemeli iskelet: bir düğümden ziyaretsiz komşuya in, dibe vur, geri çekil (özyineleme çözülür). (2) erişilebilirlik O(E): ebeveyn ağacı P(v) ile kaynaktan bir yol — en kısa DEĞİL; DFS yalnız erişilebilir kenarlara dokunur. (3) bağlı bileşenler: full DFS tüm düğümler üzerinde döngü → her ada bir DFS ağacıyla O(V+E)’de bulunur. (4) DAG + topolojik sıra: yönlü çevrimsiz çizgede ters bitiş sırası = topolojik sıralama (u→v ⇒ f(u)<f(v)), benzersiz değil. (5) çevrim tespiti: geri kenar (v’den atasına kenar) bir çevrimi tamamlar; topolojik sıra var ancak ve ancak DAG. Sonuç: tek özyinelemeli iskelet, dört güç.

Builder Notu — Tek İskelet, Dört Güç

DFS, “derine in, geri çekil” diyen tek bir özyinelemeli iskelettir — ama o tek iskeletten dört ayrı güç çıkar. Önce nasıl gezdiğini (özyineleme), sonra ne sorabildiğini (erişilebilirlik, bileşenler, sıra, çevrim) sorarız.

İleriye → topolojik sıralama her yerde: make, paket yöneticileri (npm/pip bağımlılık çözümü), build sistemleri, görev zamanlayıcılar — hepsi DAG’da topolojik sıralama çalıştırır.
İleriye → çevrim tespiti: deadlock tespiti, döngüsel bağımlılık uyarısı (import cycle), elektronik tablo formül döngüsü.
Geriye → BFS (Ders 13): ikisi de $O(V + E)$ çizge gezme iskeleti; BFS en kısa yol (ağırlıksız) verir, DFS yapısal sorular (DAG mı? bileşenler? sıra?) için.
İleriye → Dijkstra (Ders 16-19 (L11-L13)): DFS/BFS ağırlıksız; ağırlık girince öncelik kuyruğu gelir.

Tek cümle: DFS, çizgeyi özyinelemeli olarak derinlemesine gezer; bu tek iskeletten erişilebilirlik ($O(E)$), bağlı bileşenler ($O(V + E)$) ve topolojik sıralama/çevrim tespiti çıkar.

16.2 1. BFS’ten DFS’e: İki Arama Stratejisi

İki temel çizge gezme tekniği vardır. BFS kaynaktan dışa eşmerkezli daireler çizer: önce $L_1$ (uzaklık 1), tüm $L_1$ bitmeden $L_2$’ye geçilmez. DFS ise tam tersi: ilk düğümden başlar, gidebildiği kadar derine koşar, tıkanınca geri çekilir (backtrack).

“shooting outward until we reach the outer boundary, and then exploring the graph that way.” — Solomon, 6:55

İkisi de aynı çizge terminolojisi üzerine kurulu: $G = (V, E)$, $\text{Adj}^{+}(u)$ çıkış komşuları, yol (path), basit yol (simple path — aynı düğüm iki kez yok). “Doğrusal zaman” çizgede $O(V + E)$ demektir (girdiyi saklamak için gereken yer).

Şekil 16.2 aynı 7 düğümlü çizge üzerinde iki stratejiyi yan yana koyar: solda BFS dalga dalga (seviye tonları + eşmerkezli halkalar), sağda DFS tek bir kıvrımlı izle dibe dalar (ziyaret sırası $a \to b \to d \to c \to e \to f \to g$) ve tıkanınca geri çekilir.

Şekil 16.2: İki arama stratejisi — AYNI çizge: BFS dalga dalga · DFS dibe dalar (L10 §1, İMZA figür). SOL panel BFS = kaynaktan eşmerkezli halkalar, katman katman (önce TÜM L1={b,c}, sonra TÜM L2={d,e}…); her düğüm seviye tonuyla (L0 a amber kaynak → L4 g beyaz+slate). SAĞ panel DFS = aynı çizge, tek AMBER kıvrımlı ok zinciri dibe dalar (ziyaret sırası a→b→d→c→e→f→g; her ok üstünde sıra numarası); sona varınca geri-çekilme (kesikli gri geri-oklar, özyineleme yığını boşalır). Kontrast: BFS b ve c’yi BİRLİKTE (aynı katman) görür; DFS b’den HEMEN d’ye dalar, c’ye ancak geri çekilince 4. sırada varır. BFS = ağırlıksız en kısa yol; DFS = yapısal sorular (DAG mı? bileşenler? topolojik sıra? çevrim?). Veri MOTORDAN: bfs_levels(build_example_graph(),‘a’)=[[a],[b,c],[d,e],[f],[g]]; dfs_visit_order(…,‘a’)[‘order’]=[a,b,d,c,e,f,g] (Solomon 6:55).

16.3 2. Erişilebilirlik Problemi ve Ebeveyn Ağacı

Erişilebilirlik (reachability): bir kaynak $s$’den yönlü kenarları izleyerek hangi düğümlere ulaşılır?

“the reachability problem is just asking, which nodes can I reach from a given source?” — Solomon, 8:20

BFS ile çözülebilir (erişilemeyen düğümün mesafesi $\infty$), ama daha doğrudan bir yol var. “Kanıt” istersek (sadece “ulaşılır” değil, “nasıl”), her düğümü öncülü (predecessor) $P(v)$ ile etiketleriz — kaynaktan o düğüme giden bir yolda önceki düğüm. Yolu, $P$’yi geriye izleyip listeyi ters çevirerek kurarız.

Önemli fark (Ders 13’ün en kısa yol ağacından): buradaki ebeveyn ağacı en kısa yolu garanti etmez — erişilebilirlikte yolun kısalığı umurumuzda değil, sadece varlığı. Yine de bir ağaçtır (çevrim olamaz).

16.4 3. DFS Algoritması

DFS özyinelemeli bir visit fonksiyonudur: kaynağı işaretle; her komşu $v$ için, henüz ziyaret edilmemişse ($P(v) = \text{None}$) ebeveynini “ben” yap ve özyinelemeli olarak ona in.

Çalışılan Örnek — gezinme sırası. Kaynak 1’den başla. 1’in tek komşusu 2 → visit(2). 2’nin komşuları 3 ve 5; önce 3 → visit(3) → visit(4). Özyineleme dibe vurdu, geri çekil. 2 sonraki komşusu 5’e iner → visit(5). Sıra: $1 \to 2 \to 3 \to 4 \to (\text{geri}) \to 5$. Dikkat: bu seviye kümelerini izlemez — DFS dibe (4) gidip sonra 2’ye geri sarıp 5’i çağırdı. “Geri çekilme” = özyinelemenin çözülmesi.

def dfs(adj, s, parent=None):
    if parent is None:
        parent = {s: None}        # kaynagi ziyaret et
    for v in adj[s]:
        if v not in parent:       # henuz ziyaret edilmemis
            parent[v] = s         # ebeveyni = ben
            dfs(adj, v, parent)   # ozyinele
    return parent

Şekil 16.3 bu çalışılan örneği adım adım izler: üstte yönlü çizge ($1 \to 2 \to 3 \to 4$ dibe in, sonra geri çekilip 5’e dal), altta olay şeridi — in/out olaylarının sırası, $\text{out}(4), \text{out}(3)$ olaylarının $\text{in}(5)$’ten önce gelmesi (dibe vur, geri sar, sonra 5).

Şekil 16.3: DFS çalışılan örnek: 1→2→3→4 dibe in, sonra geri çekilip 5’e dal (L10 §3, İMZA figür). ÜST: yönlü çizge — kenarlar 1→2, 2→3, 2→5, 3→4. Ziyaret (ileri) okları AMBER + sıra numarası: 1→2 [1], 2→3 [2], 3→4 [3], sonra 2→5 [4]. Geri-çekilme okları KESİKLİ GRİ: 4→3, 3→2 (özyineleme çözülmesi; 5 ziyaretinden ÖNCE). ALT: olay şeridi — in(1) in(2) in(3) in(4) out(4) out(3) in(5) out(5) out(2) out(1); ‘in’ amber dolu, ‘out’ soluk çerçeve. out(4) ve out(3), in(5)’ten ÖNCE: dibe vur (4), geri sar (out 4,3), sonra 5. Seviye kümeleri İZLENMEZ — geri çekilme = özyinelemenin çözülmesi (out’lar in’lerin TERSİ sırada kapanır). Veri MOTORDAN: dfs_visit_order(build_dfs_example(),1)[‘order’]=[1,2,3,4,5]; events=[in1,in2,in3,in4,out4,out3,in5,out5,out2,out1] (Solomon L10 §3).

16.5 4. DFS Doğruluğu

İddia: DFS, erişilebilir her $v$’yi ziyaret eder ve ebeveynini doğru atar.

Çalışılan Örnek — kaynağa uzaklık üzerinden tümevarım. Kaynağa uzaklık $k$ üzerinden tümevarım.

Temel ($k = 0$): uzaklık 0 olan tek düğüm kaynağın kendisidir; algoritma ilk satırda onu doğru kurar. ✓
Adım ($k \to k+1$): $v$, kaynaktan uzaklık $k+1$ olsun. En kısa yolda $v$’den bir önceki düğüm $u$’nun uzaklığı $k$’dır → tümevarım varsayımıyla $u$ doğru ziyaret edilir. visit($u$) çağrıldığında, $v \in \text{Adj}^{+}(u)$ olduğundan DFS $v$’yi değerlendirir. İki durum: ya $P(v) \neq \text{None}$ (zaten uygun bir ebeveyn bulunmuş) ya da $P(v) = \text{None}$ (bir sonraki satır ebeveyni doğru atar). Her iki durumda da $v$’nin ebeveyni doğru. ✓

Sezgisel olarak basit; biçimsel tümevarım totoloji gibi hissettirebilir ama değil.

16.6 5. DFS Çalışma Süresi O(E)

Her düğüm en fazla bir kez ziyaret edilir (visit her düğüm için bir kez çağrılır); her kenar en fazla bir kez gezilir (kenarın “çıkış” düğümü bir kez ziyaret edildiğinden). Önemli ayrım: BFS, başta $O(V)$ yer ayırdığı için $O(V + E)$’dir; DFS ise yalnızca erişilebilir kenarlara dokunur, hiç erişilemeyen düğümü görmez → $O(E)$.

“depth-first search… it just takes order e time.” — Solomon, 22:09

(Kenarsız bir çizgede BFS yine $O(V)$, DFS ise $O(E) = O(0)$ işi yapar; sınırlar birebir aynı değildir.)

16.7 6. DFS En Kısa Yol Vermez

DFS’in ürettiği yol en kısa olmak zorunda değildir.

“there’s no reason why the path that we get should be the shortest.” — Solomon, 24:01

Uç örnek: bir çevrim çizgesi (büyük halka). Kaynaktan başlayıp komşu komşuyu özyinelemeli çağırırsak, son düğüme 4 düğümlük bir zincirin arkasından varırız — oysa tek bir kenarla doğrudan gidilebilirdi. DFS o kenarı seçmedi. Bu yüzden ağırlıksız en kısa yol için BFS kullanılır; DFS yapısal sorular içindir.

16.8 7. Bağlılık ve Bağlı Bileşenler

Bir çizge bağlı (connected) ise her düğümden her düğüme bir yol vardır.

“a graph is connected if there’s a path getting from every vertex to every other vertex.” — Solomon, 25:14

Yönlü çizgede bağlılık tuhaftır ($u \to v$ var ama $v \to u$ yok olabilir), bu yüzden çoğunlukla yönsüz çizgelerde konuşulur: düğümler “kümeler” hâlinde gelir — bir bağlı bileşen (connected component).

Bağlı bileşenler problemi: tüm kümeleri listele. Çözüm full DFS: tüm düğümler üzerinde bir döngü; düğüm henüz ziyaret edilmemişse ondan DFS başlat (o bileşeni “flood fill” eder), topla, devam et. Her kenar en fazla bir kez gezilir (bir düğüm iki bileşende olamaz) → $O(V + E)$.

def full_dfs(adj, V):
    parent = {}
    components = []
    for s in V:                   # tum dugumler uzerinde dongu
        if s not in parent:       # yeni bilesen
            parent[s] = None
            dfs(adj, s, parent)
            components.append(s)   # bu bilesenin temsilcisi
    return components, parent

Şekil 16.4 full DFS’i “ada keşfi” olarak gösterir: üç bağlı bileşen ($\{1,2,3\}$, $\{4,5\}$, $\{6\}$), her birinin temsilci kökü ($1, 4, 6$), ve altta dış-döngünün düğümleri sırayla tarayışı (ziyaretsiz köke yeni DFS başlat, görülmüşü atla).

Şekil 16.4: Full DFS = bağlı bileşenler: ziyaretsiz her köke yeni DFS başlat (ada ada) (L10 §7, İMZA figür). ÜST: 3 ada çizgesi — küme 1 {1,2,3} (üçgen-vari, amber halo, bileşen C₁), küme 2 {4,5} (çift, slate halo, C₂), küme 3 {6} (tek düğüm, beyaz halo, C₃); her ada altında bileşen etiketi. Temsilci kökler (her bileşenin ilk ziyaret edilen düğümü) amber dolgulu + ‘kök’ etiketi: 1, 4, 6. ALT: full DFS dış-döngü şeridi — düğümler 1..6 SIRAYLA taranır; 1 ziyaretsiz → DFS başlat (ada 1’i sular), 2,3 görülmüş → atla, 4 ziyaretsiz → DFS başlat (ada 2), 5 atla, 6 ziyaretsiz → DFS başlat (ada 3); amber ‘DFS’ rozeti her başlatmada. Dış döngü her düğüme 1 kez bakar + her kenar en fazla 1 kez gezilir → O(V+E). Veri MOTORDAN: connected_components=[[1,2,3],[4,5],[6]]; full_dfs temsilcileri=[1,4,6] (Solomon L10 §7).

16.9 8. Yönlü Çevrimsiz Çizge (DAG) ve Topolojik Sıralama

Bir DAG (Directed Acyclic Graph): yönlü kenarlı, çevrimsiz çizge. (Yönlendirilmiş bir ağaç bir DAG örneğidir.)

“a DAG is a Directed Acyclic Graph.” — Solomon, 32:28

Topolojik sıralama: her düğüme bir sıra indeksi $f$ atayan, şu özelliği sağlayan bir düzen: her $u \to v$ kenarı için $f(u) < f(v)$ ($u$, $v$’den önce gelir).

“if I have a directed edge from u to v, then f of u is less than f of v.” — Solomon, 34:46

Topolojik sıralama benzersiz değildir — $A \to B$, $A \to C$, $B \to D$, $C \to D$ çizgesinde hem “A C B D” hem “A B C D” geçerlidir. Bu “özgürlük”, algoritmanın çoktan birini bulmasına izin verir.

16.10 9. Bitiş Sırası → Topolojik Sıralama

Bitiş sırası (finishing order): full DFS çalıştır; bir düğümün visit çağrısı tamamlandığında (tüm komşuları gezildiğinde) onu sıraya ekle. İddia: bir DAG’da, bitiş sırasının tersi geçerli bir topolojik sıralamadır.

“the reverse of the finishing order is a topological order.” — Solomon, 37:54

Çalışılan Örnek — kanıt (iki durum). Bir $u \to v$ kenarı al; ters bitiş sırasında $u$’nun $v$’den önce geldiğini göstermeliyiz.

Durum 1 — $u$, $v$’den önce ziyaret edildi: visit($u$), $v$’yi (henüz ziyaretsizse) çağırır; visit($v$), visit($u$)’dan önce tamamlanır. Ters sırada bu, $u$’yu $v$’nin önüne koyar. ✓
Durum 2 — $v$, $u$’dan önce ziyaret edildi: çizge çevrimsiz olduğundan $v$’den $u$’ya yol yoktur (olsaydı çevrim olurdu). O hâlde visit($v$), $u$’yu hiç görmeden tamamlanır → Durum 1’le aynı sonuç: ters sırada $u$, $v$’den önce. ✓

Şekil 16.5 bu mekanizmayı gösterir: örnek DAG, full DFS’in bitiş sırası $[D, B, C, A]$ (D yaprak, ilk biter; A kök, son biter), ve onun tersi = topolojik sıra $[A, C, B, D]$; her DAG kenarı için $f(u) < f(v)$ onayı yeşil rozetle, ve “benzersiz değil” notu ($[A, B, C, D]$ de geçerli).

Şekil 16.5: DAG’da topolojik sıra = TERS bitiş sırası (tek DFS geçişi, O(V+E)) (L10 §8-9, İMZA figür). ÜST-SOL: örnek DAG — A üstte, B ve C ortada yan yana, D altta (elmas); yönlü oklar A→B, A→C, B→D, C→D. ORTA serit: BİTİŞ SIRASI (visit tamamlanınca out() ile eklenir) [D, B, C, A]; D ilk biter (yaprak), A son biter (kök). ‘TERSE ÇEVİR’ dönüş oku. ALT serit: TOPOLOJİK SIRA = ters bitiş = [A, C, B, D] (amber kutular); her DAG kenarı için f(u)<f(v) onayı yeşil ✓ rozeti (A<C, A<B, B<D, C<D); verify_topological=True. YAN NOT: topolojik sıra BENZERSİZ DEĞİL — [A, C, B, D] ve [A, B, C, D] ikisi de geçerli (B-C arası kenar yok); ters bitiş bunlardan BİRİNİ bulur. Kanıt iki durum (Solomon 37:54). Veri MOTORDAN: build_dag_example={A:[B,C],B:[D],C:[D],D:[]}; finishing_order=[D,B,C,A]; topological_order=[A,C,B,D]; verify=True.

16.11 10. Çevrim Tespiti

DAG değilsek topolojik sıralama elde edemeyiz. Yani: ters bitiş sırasını hesapla, sonra her kenarın $f(u) < f(v)$ ilişkisine uyup uymadığını kontrol et. Uymayan bir kenar bulursak çizge DAG değildir → bir çevrim vardır. (Aslında: topolojik sıralama var $\iff$ çizge DAG.)

Çevrimi yalnızca tespit değil bulmak için: $G$ çevrim içeriyorsa, full DFS bir $v$ düğümünden onun bir atasına (ancestor) giden bir kenar gezer (atası = özyineleme ağacında $v$’den önce gelen düğüm).

“full DFS will traverse an edge from a vertex v to some ancestor of v.” — Solomon, 48:20

Kanıt taslağı: çevrim $v_0 \to v_1 \to \ldots \to v_k \to v_0$ olsun; $v_0$’ı DFS’in ilk gördüğü düğüm seç. $v_0$’ın özyineleme ağacı tamamlanmadan, ondan erişilebilen $v_1, \ldots, v_k$ de tamamlanır; $v_k$ komşularını gezerken $v_0$ kenarını görür — bu, $v_k$’den atası $v_0$’a giden geri kenardır (back edge). DFS sırasında bu geri kenarı yakaladığın an çevrimi bulmuş olursun.

Şekil 16.6 bu ayrımı iki panelle gösterir: solda çevrimli çizge ($1 \to 2 \to 3 \to 1$ + $4 \to 1$), DFS yığını $1 \to 2 \to 3$ aktifken $3 \to 1$ bir geri kenardır (1, 3’ün atası) → çevrim $[1,2,3,1]$, DAG değil; sağda $3 \to 1$ kaldırılmış, geri kenar yok → DAG, topolojik sıra $[4,1,2,3]$.

Şekil 16.6: Çevrim tespiti: geri kenar (aktif yığındaki ataya kenar) = çevrim (L10 §10, İMZA figür). SOL panel — çevrimli çizge: 1→2→3→1 üçgeni + 4→1 dış kenarı. DFS özyineleme yolu 1→2→3 amber (aktif yığın). 3’ten 1’e giden kenar KALIN AMBER KESİKLİ + ‘geri kenar (back edge)’ etiketi — 1, 3’ün ATASIDIR (özyineleme yığınında hâlâ aktif). Sonuç: ÇEVRİM VAR → DAG DEĞİL; çevrim [1,2,3,1], topolojik sıra YOK. SAĞ panel — aynı yapı ama 3→1 kenarı KALDIRILMIŞ (3 çıkışsız): DFS temiz biter, geri kenar yok, çevrim yok → DAG; ters bitiş sırası = topolojik sıra [4,1,2,3]. Full DFS çevrim varsa bir v düğümünden atasına giden kenarı gezer. Veri MOTORDAN: find_cycle({1:[2],2:[3],3:[1],4:[1]})=[1,2,3,1]; find_cycle(3→1 kaldırılmış)=None; topological_order=[4,1,2,3]; verify=True (Solomon 48:20).

16.12 Bu Dersin Özeti

DFS = özyinelemeli “derine in, geri çekil”; BFS eşmerkezli dairelerken DFS dışa fırlar.
Erişilebilirlik: ebeveyn ağacı $P(v)$ ile bir yol (en kısa değil) ver; ağaç (çevrimsiz).
DFS doğruluğu: uzaklık $k$ üzerinden tümevarım; $u$ ($k$) doğruysa $v$ ($k+1$) de doğru.
Çalışma süresi: DFS $O(E)$ (yalnız erişilebilir kenarlar); BFS $O(V + E)$ (başta $O(V)$ yer).
Bağlı bileşenler: full DFS, tüm düğümler üzerinde döngü → $O(V + E)$.
DAG + topolojik sıralama: $f(u) < f(v)$; benzersiz değil; ters bitiş sırası = topolojik sıra.
Çevrim tespiti: topolojik sıra $\iff$ DAG; geri kenar ($v \to$ atası) çevrimi verir.

Şekil 16.7 dersi tek bir sentez figüründe toplar: ortada DFS ($O(V+E)$ özyinelemeli iskelet), dört köşede dört güç — erişilebilirlik, bağlı bileşenler, topolojik sıra, çevrim tespiti — her biri motordan gelen bir mini sonuçla.

Şekil 16.7: DFS = tek özyinelemeli iskelet → dört güç (L10 sentezi, İMZA figür). ORTADA büyük amber kutu: DFS — derine in, geri çekil (özyinelemeli visit, O(V+E)). Dört köşede uydu kutusu, merkezden oklarla bağlı, her biri motordan mini sonuç: (1) ERİŞİLEBİLİRLİK O(E) — ebeveyn ağacı (kaynak 1) {1:·, 2:1, 3:2, 4:3, 5:2}, yol 1→2→3→4 en KISA DEĞİL (DFS yolu ≠ en kısa yol). (2) BAĞLI BİLEŞENLER O(V+E) — full DFS sel-doldurma → {a,b,c} {d,e} {f,g,h}, 3 ada. (3) TOPOLOJİK SIRA — ters bitiş sırası (DAG) A→C→B→D, her u→v’de f(u)<f(v) ✓ (build sistemleri make·npm·pip). (4) ÇEVRİM TESPİTİ — geri kenar (aktif yığına) 1→2→3→1, atasına dönen kenar → çevrim (deadlock·import döngüsü). Bağımlılık çözen her sistem içten içe bunu çalıştırır. Veri MOTORDAN: dfs(build_dfs_example(),1)={1:None,2:1,3:2,4:3,5:2}; connected_components=[[a,b,c],[d,e],[f,g,h]]; topological_order(build_dag_example())=[A,C,B,D]; find_cycle({1:[2],2:[3],3:[1]})=[1,2,3,1].

Tek Bir Cümle

DFS, çizgeyi özyinelemeli olarak derinlemesine gezen tek bir iskelettir; ondan erişilebilirlik ($O(E)$), bağlı bileşenler ve topolojik sıralama/çevrim tespiti — hepsi $O(V + E)$ içinde — doğal olarak türer.

16.13 Kontrol Soruları

Soru 1: DFS ile BFS arasındaki temel davranış farkı nedir, ve neden DFS O(E) iken BFS O(V+E)?

Cevap: BFS, kaynaktan dışa katman katman (seviye kümeleri) ilerler — bir seviye bitmeden sonrakine geçmez. DFS, bir dalda olabildiğince derine iner, tıkanınca geri çekilir. Süre farkı uygulamadan gelir: bu dersteki BFS başta $O(V)$ yer ayırdığı için (erişilemeyenler dahil) $O(V + E)$’dir; DFS yalnızca kaynaktan erişilebilen kenarlara dokunur, hiç erişilemeyen düğümü görmez, dolayısıyla $O(E)$. (full DFS ise tüm düğümler üzerinde döngü kurduğundan yine $O(V + E)$.)

Soru 2: DFS’in ürettiği ebeveyn ağacı neden en kısa yolu vermez? Bir örnek ver.

Cevap: DFS, bir komşuya “ilk denk geldiği” sırada iner — bu sıra en kısa yolu izlemez. Çevrim çizgesi (halka) uç örnektir: kaynaktan komşu komşuyu özyinelemeli çağırınca son düğüme uzun bir zincirin arkasından varılır, oysa tek kenarla doğrudan gidilebilirdi. DFS o kısa kenarı seçmez. Bu yüzden ağırlıksız en kısa yol için BFS kullanılır; DFS yapısal sorular (DAG mı, bileşenler, sıra) içindir.

Soru 3: “Ters bitiş sırası = topolojik sıralama” iddiasında, v’nin u’dan önce ziyaret edildiği durum neden çevrimsizliğe dayanır?

Cevap: $u \to v$ kenarı var. $v$ önce ziyaret edildiyse, visit($v$) tamamlanmadan $u$’yu görür mü? Görmesi için $v$’den $u$’ya bir yol gerekir — ama $u \to v$ zaten var, $v \to \ldots \to u$ olsaydı bir çevrim oluşurdu. Çizge DAG (çevrimsiz) olduğundan bu imkânsız. O hâlde visit($v$), $u$’yu hiç görmeden tamamlanır; ters bitiş sırasında $u$, $v$’den önce gelir (Durum 1 ile aynı sonuç). Çevrimsizlik olmasaydı iddia çökerdi.

Soru 4: Bir çizgenin DAG olup olmadığını ve (varsa) bir çevrimini nasıl bulursun?

Cevap: full DFS ile ters bitiş sırasını hesapla; her kenar $f(u) < f(v)$ ilişkisine uyuyorsa çizge bir DAG’dır (topolojik sıralama var $\iff$ DAG). Bir kenar bu ilişkiyi bozuyorsa çizge DAG değildir → çevrim vardır. Çevrimi bulmak için DFS sırasında bir düğümden atasına giden bir kenar (geri kenar, back edge) ara; o geri kenar bulunduğu an, atadan o düğüme inen özyineleme zinciri + geri kenar bir çevrim oluşturur.

16.14 Egzersizler

Egzersiz 1. Verilen yönlü bir çizgede, belirli bir kaynaktan DFS gezinme sırasını ve ebeveyn ağacı $P$’yi elle çıkar; aynı çizgede BFS sırasıyla karşılaştır.

Egzersiz 2. Python’da özyinelemeli DFS’i (yukarıdaki dfs) yığın (stack) tabanlı özyinelemesiz bir sürüme dönüştür; çıktının ebeveyn ağacının aynı kaldığını doğrula.

Egzersiz 3. full DFS ile bir yönsüz çizgenin bağlı bileşen sayısını hesaplayan bir fonksiyon yaz; süresinin $O(V + E)$ olduğunu argümanla göster.

Egzersiz 4. Küçük bir DAG için tüm geçerli topolojik sıralamaları elle listele; ters bitiş sırasının bunlardan biri olduğunu doğrula.

Egzersiz 5. DFS’i, bir geri kenar (atası ziyarette olan bir komşu) bulduğunda çevrimi düğüm listesi olarak döndürecek şekilde genişlet.

16.15 Sonraki Ders İçin Hazırlık

Sonraki: Ders 16 (L11) — Ağırlıklı En Kısa Yollar

Ders 16 (L11): Ağırlıklı En Kısa Yollar — Jason Ku ile, kenarlara ağırlık ekliyoruz: artık “en az kenar” değil, “en az toplam ağırlık” arıyoruz. BFS/DFS yetmez; ağırlıklar (hatta negatif ağırlıklar) yeni problemler doğurur. Bu, Bellman-Ford ve Dijkstra’ya giden kapının açılışıdır.

Ders 16 Öncesi Yapılacak:

Bu dersin egzersizlerini, özellikle Egzersiz 3 (bağlı bileşenler) ve 4 (topolojik sıralama) çöz.
DFS doğruluk kanıtını (uzaklık $k$ tümevarımı) ezberden anlat.
Ana cümleyi tekrar oku: “DFS tek iskelet; erişilebilirlik, bileşenler, topolojik sıra ondan türer.”

16.16 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Sayfada
DFS	Özyinelemeli “derine in, geri çekil”; ebeveyn ağacı $P(v)$	Böl. 1, 3
Erişilebilirlik	$s$’den ulaşılan düğümler; $P$ ile bir yol (en kısa değil)	Böl. 2
DFS süresi	$O(E)$ (yalnız erişilebilir kenarlar); full DFS $O(V + E)$	Böl. 5, 7
Bağlı bileşen	Yönsüz çizgede birbirinden erişilebilir küme; full DFS	Böl. 7
DAG	Yönlü + çevrimsiz çizge	Böl. 8
Topolojik sıra	$u \to v \Rightarrow f(u) < f(v)$; benzersiz değil	Böl. 8
Bitiş sırası	visit tamamlanınca ekle; tersi = topolojik sıra	Böl. 9
Çevrim tespiti	geri kenar ($v \to$ atası); topolojik sıra $\iff$ DAG	Böl. 10

16.17 Builder ve OMSCS Bağlantıları

6 köprü

Bu ders, “tek özyinelemeli iskelet (DFS), dört güç” sezgisini kurar — köprülerin özeti:

Topolojik sıralama → build sistemleri (make, Bazel), paket bağımlılığı (npm/pip), görev zamanlama: DAG’da çalıştırma sırası.
Çevrim tespiti → deadlock, import döngüsü, elektronik tablo formül döngüsü, derleyici bağımlılık grafı.
Bağlı bileşenler → kümeleme, sosyal ağ grupları, görüntü “flood fill”, birlik-bul (union-find) alternatifi.
DFS özyineleme → ağaç/çizge gezme, geri izleme (backtracking) algoritmaları, ifade ağacı değerlendirme.
Erişilebilirlik → ulaşılabilir kod analizi (derleyici), çöp toplama (mark-and-sweep), bağımlılık kapanışı.
$O(V + E)$ doğrusal → seyreklik bilinci: gerçek çizgeler seyrek; bir gezinmede her kenara bir kez dokun.

Tek bir şey alıp gideceksen

DFS, “derine in, geri çekil” diyen tek bir özyinelemeli iskelettir — ama o tek iskeletten erişilebilirlik ($O(E)$), bağlı bileşenler ($O(V + E)$), topolojik sıralama ve çevrim tespiti çıkar. Bağımlılık çözen her sistem (make, paket yöneticisi, derleyici) içten içe bunu çalıştırır.

--- title: "Derinlemesine Arama (DFS)" subtitle: "DFS = özyinelemeli derine in, geri çekil; erişilebilirlik O(E) (ebeveyn ağacı, en kısa değil); full DFS → bağlı bileşenler O(V+E); DAG'da ters bitiş sırası = topolojik sıra (u→v ⇒ f(u)<f(v), benzersiz değil); geri kenar (v → atası) = çevrim; bağımlılık çözen her sistem (make/npm/pip) içten içe bunu çalıştırır" --- ::: {.callout-note title="Bölüm bilgisi"} - **Solomon'un videosu:** [YouTube — Lecture 10: Depth-First Search](https://www.youtube.com/watch?v=IBfWDYSffUU) (≈52 dk) - **OCW sayfası:** [MIT 6.006 Lecture 10: Depth-First Search](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-10-depth-first-search/) - **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 15 (L10) - **Hoca:** Justin Solomon (Demaine/Ku değil) - **Okuma süresi:** ≈25 dk > Bir önceki ders BFS'i (enine arama) verdi; bu ders onun kardeşi **DFS**'i çözer ve üç güçlü uygulamayı açar: erişilebilirlik, bağlı bileşenler, topolojik sıralama (+ çevrim tespiti). ::: ## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d15} Ders 13 (L9) BFS'i (enine arama) verdi; Ders 14 (Quiz 1 Gözden Geçirme, Jason Ku) araya girdi. Bugün yine Justin Solomon ile BFS'in kardeşi **DFS (depth-first search, derinlemesine arama)** ile devam ediyoruz. DFS, çizgeyi "olabildiğince derine in, sonra geri çekil" mantığıyla gezer ve üç güçlü uygulamayı açar: **erişilebilirlik**, **bağlı bileşenler**, **topolojik sıralama** (+ çevrim tespiti). > *"in breadth-first search, we're like, drawing concentric circles. In depth-first search... we're like, shooting outward until we reach the outer boundary."* — Solomon, 6:55 Üç ana fikir bu derste yan yana gelir: 1. **DFS = özyinelemeli gezinme** — bir düğümden komşularına in, her komşu kendi komşularına insin; erişilebilirliği $O(E)$'de çöz. 2. **Bağlı bileşenler** — full DFS (her düğüm üzerinde döngü) ile $O(V + E)$'de tüm "kümeleri" bul. 3. **Topolojik sıralama** — bir DAG'da, DFS bitiş sırasının **tersi** geçerli bir bağımlılık sıralaması verir; aynı teknik **çevrim tespiti** yapar. ```{mermaid} %%| label: fig-concept-map %%| echo: false %%| fig-cap: "Ders 15'in (L10) kavram haritası: kök = derinlemesine arama (DFS). Beş dal — (1) DFS özyinelemeli iskelet: bir düğümden ziyaretsiz komşuya in, dibe vur, geri çekil (özyineleme çözülür). (2) erişilebilirlik O(E): ebeveyn ağacı P(v) ile kaynaktan bir yol — en kısa DEĞİL; DFS yalnız erişilebilir kenarlara dokunur. (3) bağlı bileşenler: full DFS tüm düğümler üzerinde döngü → her ada bir DFS ağacıyla O(V+E)'de bulunur. (4) DAG + topolojik sıra: yönlü çevrimsiz çizgede ters bitiş sırası = topolojik sıralama (u→v ⇒ f(u)<f(v)), benzersiz değil. (5) çevrim tespiti: geri kenar (v'den atasına kenar) bir çevrimi tamamlar; topolojik sıra var ancak ve ancak DAG. Sonuç: tek özyinelemeli iskelet, dört güç." flowchart TD A["Ders 15 (L10): Derinlemesine Arama (DFS)"] --> D["DFS özyinelemeli iskelet derine in, geri çekil"] D --> D1["ziyaretsiz komşuya in dibe vur, geri çekil (yığın boşalır)"] A --> R["erişilebilirlik O(E) ebeveyn ağacı P(v)"] R --> R1["kaynaktan bir yol — en KISA değil yalnız erişilebilir kenarlara dokunur"] A --> C["bağlı bileşenler full DFS"] C --> C1["tüm düğümler üzerinde döngü her ada bir DFS ağacı, O(V+E)"] A --> T["DAG + topolojik sıra ters bitiş sırası"] T --> T1["u→v ⇒ f(u)<f(v) benzersiz değil"] A --> Y["çevrim tespiti geri kenar"] Y --> Y1["v'den atasına kenar = çevrim topolojik sıra var ancak ve ancak DAG"] 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 D,R,C,T,Y branch class D1,R1,C1,T1,Y1 leaf ``` ::: {.callout-tip title="Builder Notu — Tek İskelet, Dört Güç"} DFS, "derine in, geri çekil" diyen tek bir özyinelemeli iskelettir — ama o tek iskeletten dört ayrı güç çıkar. Önce nasıl gezdiğini (özyineleme), sonra ne sorabildiğini (erişilebilirlik, bileşenler, sıra, çevrim) sorarız. - **İleriye → topolojik sıralama her yerde:** `make`, paket yöneticileri (npm/pip bağımlılık çözümü), build sistemleri, görev zamanlayıcılar — hepsi DAG'da topolojik sıralama çalıştırır. - **İleriye → çevrim tespiti:** deadlock tespiti, döngüsel bağımlılık uyarısı (import cycle), elektronik tablo formül döngüsü. - **Geriye → BFS (Ders 13):** ikisi de $O(V + E)$ çizge gezme iskeleti; BFS en kısa yol (ağırlıksız) verir, DFS yapısal sorular (DAG mı? bileşenler? sıra?) için. - **İleriye → Dijkstra (Ders 16-19 (L11-L13)):** DFS/BFS ağırlıksız; ağırlık girince öncelik kuyruğu gelir. Tek cümle: *DFS, çizgeyi özyinelemeli olarak derinlemesine gezer; bu tek iskeletten erişilebilirlik ($O(E)$), bağlı bileşenler ($O(V + E)$) ve topolojik sıralama/çevrim tespiti çıkar.* ::: ```{python} #| echo: false # ============================================================================ # SETUP — 6.006 Ders 15 (L10) DFS motoru (_engine.py D15 bölümü: dfs'ten # build_dag_example'a) + D13 build_example_graph / bfs / bfs_levels # (fig-bfs-vs-dfs için) + 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 dfs / dfs_visit_order / full_dfs / connected_components / # finishing_order / topological_order / verify_topological / find_cycle / # build_dfs_example / build_dag_example / build_example_graph / bfs / # bfs_levels / make_undirected + COL_*'ı 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. # ============================================================================ import math from collections import deque import matplotlib.pyplot as plt from matplotlib.patches import Circle, FancyBboxPatch, FancyArrowPatch, Arc, Ellipse # --------------------------------------------------------------------------- # _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) — fig-bfs-vs-dfs için gereken BFS yardımcıları. # 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. 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.""" 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 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 build_example_graph(): """L9 figürleri için deterministik yönsüz örnek (7 düğüm, 8 kenar).""" return make_undirected([("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"), ("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")]) # --------------------------------------------------------------------------- # _engine.py D15 (L10) — Derinlemesine Arama (DFS) — Solomon # DFS = özyinelemeli "derine in, geri çekil"; erişilebilirlik O(E) # (ebeveyn ağacı — en kısa DEĞİL); full DFS → bağlı bileşenler O(V+E); # DAG'da TERS BİTİŞ SIRASI = topolojik sıra; geri kenar (v → atası) = çevrim. # --------------------------------------------------------------------------- def dfs(adj, s, parent=None): """DFS (L10 §3): kaynağı işaretle; ziyaretsiz her komşuya in. O(E).""" if parent is None: parent = {s: None} for v in adj[s]: if v not in parent: # henüz ziyaret edilmemiş parent[v] = s dfs(adj, v, parent) return parent def dfs_visit_order(adj, s): """fig-dfs-run için: ziyaret sırası + geri-çekilme olayları.""" parent = {s: None} order, events = [], [] def visit(u): order.append(u) events.append(("in", u)) for v in adj[u]: if v not in parent: parent[v] = u visit(v) events.append(("out", u)) visit(s) return {"order": order, "events": events, "parent": parent} def full_dfs(adj): """Full DFS (L10 §7): tüm düğümler üzerinde döngü → bileşenler. O(V+E).""" parent, components = {}, [] for s in adj: if s not in parent: parent[s] = None dfs(adj, s, parent) components.append(s) return parent, components def connected_components(adj): """Yönsüz çizgede bileşen kümeleri (sıralı listeler — deterministik).""" seen, comps = set(), [] for s in adj: if s in seen: continue comp = {s} stack = [s] while stack: u = stack.pop() for v in adj[u]: if v not in comp: comp.add(v) stack.append(v) seen |= comp comps.append(sorted(comp)) return comps def finishing_order(adj): """Bitiş sırası (L10 §9): full DFS; visit TAMAMLANINCA ekle.""" parent, order = {}, [] def visit(u): for v in adj[u]: if v not in parent: parent[v] = u visit(v) order.append(u) # tüm komşular bitti → bitiş for s in adj: if s not in parent: parent[s] = None visit(s) return order def topological_order(adj): """Topolojik sıra (L10 §9): TERS bitiş sırası (DAG'da geçerli).""" return list(reversed(finishing_order(adj))) def verify_topological(adj, order): """Her u→v kenarı için f(u) < f(v) mi? (L10 §8 tanımı).""" f = {v: i for i, v in enumerate(order)} return all(f[u] < f[v] for u in adj for v in adj[u]) def find_cycle(adj): """Çevrim bulma (L10 §10): DFS sırasında AKTİF yığındaki bir ataya giden geri kenar yakalanınca çevrimi döndür; DAG ise None. O(V+E).""" color = {v: 0 for v in adj} # 0 beyaz, 1 aktif (yığında), 2 bitti stack = [] def visit(u): color[u] = 1 stack.append(u) for v in adj[u]: if color[v] == 1: # geri kenar → çevrim: v ... u + (u,v) i = stack.index(v) return stack[i:] + [v] if color[v] == 0: cyc = visit(v) if cyc is not None: return cyc color[u] = 2 stack.pop() return None for s in adj: if color[s] == 0: cyc = visit(s) if cyc is not None: return cyc return None def build_dfs_example(): """L10 §3 çalışılan örneği (Solomon): 1→2; 2→3,5; 3→4. Ziyaret sırası 1,2,3,4,(geri),5 — seviye sırasını İZLEMEZ.""" return {1: [2], 2: [3, 5], 3: [4], 4: [], 5: []} def build_dag_example(): """L10 §8 örneği: A→B, A→C, B→D, C→D — topolojik sıra benzersiz DEĞİL (hem A,B,C,D hem A,C,B,D geçerli).""" return {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []} ``` ## 1. BFS'ten DFS'e: İki Arama Stratejisi {#sec-1-bfsten-dfse} İki temel çizge gezme tekniği vardır. **BFS** kaynaktan dışa **eşmerkezli daireler** çizer: önce $L_1$ (uzaklık 1), tüm $L_1$ bitmeden $L_2$'ye geçilmez. **DFS** ise tam tersi: ilk düğümden başlar, gidebildiği kadar **derine** koşar, tıkanınca **geri çekilir (backtrack)**. > *"shooting outward until we reach the outer boundary, and then exploring the graph that way."* — Solomon, 6:55 İkisi de aynı çizge terminolojisi üzerine kurulu: $G = (V, E)$, $\text{Adj}^{+}(u)$ çıkış komşuları, yol (path), basit yol (simple path — aynı düğüm iki kez yok). "Doğrusal zaman" çizgede $O(V + E)$ demektir (girdiyi saklamak için gereken yer). @fig-bfs-vs-dfs aynı 7 düğümlü çizge üzerinde iki stratejiyi yan yana koyar: solda BFS dalga dalga (seviye tonları + eşmerkezli halkalar), sağda DFS tek bir kıvrımlı izle dibe dalar (ziyaret sırası $a \to b \to d \to c \to e \to f \to g$) ve tıkanınca geri çekilir. ```{python} #| label: fig-bfs-vs-dfs #| fig-cap: "İki arama stratejisi — AYNI çizge: BFS dalga dalga · DFS dibe dalar (L10 §1, İMZA figür). SOL panel BFS = kaynaktan eşmerkezli halkalar, katman katman (önce TÜM L1={b,c}, sonra TÜM L2={d,e}…); her düğüm seviye tonuyla (L0 a amber kaynak → L4 g beyaz+slate). SAĞ panel DFS = aynı çizge, tek AMBER kıvrımlı ok zinciri dibe dalar (ziyaret sırası a→b→d→c→e→f→g; her ok üstünde sıra numarası); sona varınca geri-çekilme (kesikli gri geri-oklar, özyineleme yığını boşalır). Kontrast: BFS b ve c'yi BİRLİKTE (aynı katman) görür; DFS b'den HEMEN d'ye dalar, c'ye ancak geri çekilince 4. sırada varır. BFS = ağırlıksız en kısa yol; DFS = yapısal sorular (DAG mı? bileşenler? topolojik sıra? çevrim?). Veri MOTORDAN: bfs_levels(build_example_graph(),'a')=[[a],[b,c],[d,e],[f],[g]]; dfs_visit_order(...,'a')['order']=[a,b,d,c,e,f,g] (Solomon 6:55)." #| fig-width: 11.0 #| fig-height: 6.2 # fig-bfs-vs-dfs (L10 §1 İMZA): BFS dalga dalga vs DFS dibe dalar (AYNI çizge). # Veri MOTORDAN (build_example_graph / bfs_levels / dfs_visit_order). COL_* / plt # gizli setup hücresinden. Çizge çizimi networkx KULLANMAZ — elle koordinat. _BVD_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), } _BVD_EDGES = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d"), ("c", "e"), ("d", "f"), ("e", "f"), ("f", "g")] _BVD_R = 0.22 _BVD_LEVEL_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 ] def _bvd_bfs_panel(ax, levels, src): level_of = {v: k for k, lvl in enumerate(levels) for v in lvl} sx, sy = _BVD_POS[src] for k in range(1, len(levels)): rr = max(math.hypot(_BVD_POS[v][0] - sx, _BVD_POS[v][1] - sy) for v in levels[k]) + _BVD_R + 0.10 ax.add_patch(Arc((sx, sy), 2 * rr, 2 * rr, theta1=-80, theta2=12, edgecolor=COL_AMBER_600, linewidth=1.3, linestyle=(0, (3, 3)), alpha=0.55, zorder=0)) ang = math.radians(-34) ax.text(sx + rr * math.cos(ang) + 0.10, sy + rr * math.sin(ang) - 0.02, f"L{k}", ha="left", va="center", fontsize=8, color=COL_AMBER_700, weight="bold", alpha=0.85, zorder=1) for u, v in _BVD_EDGES: x0, y0 = _BVD_POS[u] x1, y1 = _BVD_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 _BVD_POS.items(): fc, ec, tcol = _BVD_LEVEL_STYLE[level_of[v]] ax.add_patch(Circle((x, y), _BVD_R, facecolor=fc, edgecolor=ec, linewidth=3.0 if v == src else 2.2, zorder=5)) ax.text(x, y, v, ha="center", va="center", fontsize=12, color=tcol, weight="bold", zorder=6) ax.text(sx - _BVD_R - 0.12, sy + _BVD_R + 0.08, "kaynak", ha="right", va="bottom", fontsize=8.5, color=COL_AMBER_700, weight="bold", style="italic", zorder=6) ax.text(0.5, 2.78, "BFS — enine arama (dalga dalga)", ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6) ax.text(0.5, -0.78, "katman katman: önce TÜM L1, sonra TÜM L2 …\n" "eşmerkezli halkalar — en kısa uzaklık δ sabitlenir", ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6) ax.set_xlim(-1.05, 3.05) ax.set_ylim(-1.15, 3.05) ax.set_aspect("equal") ax.axis("off") def _bvd_dfs_panel(ax, order, src): for u, v in _BVD_EDGES: x0, y0 = _BVD_POS[u] x1, y1 = _BVD_POS[v] ax.plot([x0, x1], [y0, y1], color=COL_SLATE_400, linewidth=1.4, zorder=1, alpha=0.7, solid_capstyle="round") for i in range(len(order) - 1): u, v = order[i], order[i + 1] x0, y0 = _BVD_POS[u] x1, y1 = _BVD_POS[v] adjacent = (u, v) in _BVD_EDGES or (v, u) in _BVD_EDGES rad = 0.20 if adjacent else 0.42 ax.add_patch(FancyArrowPatch( (x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=15, color=COL_ACCENT, linewidth=2.4, zorder=4, shrinkA=14, shrinkB=14, connectionstyle=f"arc3,rad={rad}")) mx = (x0 + x1) / 2 - rad * (y1 - y0) * 0.55 my = (y0 + y1) / 2 + rad * (x1 - x0) * 0.55 ax.text(mx, my, f"{i + 1}→{i + 2}", ha="center", va="center", fontsize=6.5, color=COL_AMBER_700, weight="bold", zorder=7, bbox=dict(boxstyle="round,pad=0.10", fc=COL_WHITE, ec=COL_AMBER_300, lw=0.8)) visit_idx = {v: i + 1 for i, v in enumerate(order)} for v, (x, y) in _BVD_POS.items(): is_src = (v == src) ax.add_patch(Circle((x, y), _BVD_R, 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=5)) ax.text(x, y, v, ha="center", va="center", fontsize=12, color=COL_AMBER_700 if is_src else COL_TEXT, weight="bold", zorder=6) ax.text(x + _BVD_R + 0.04, y + _BVD_R - 0.02, f"#{visit_idx[v]}", ha="left", va="bottom", fontsize=7, color=COL_SLATE_500, weight="bold", zorder=6) unwind = list(reversed(order)) for i in range(len(unwind) - 1): u, v = unwind[i], unwind[i + 1] x0, y0 = _BVD_POS[u] x1, y1 = _BVD_POS[v] ax.add_patch(FancyArrowPatch( (x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=9, color=COL_SLATE_500, linewidth=1.1, zorder=3, linestyle=(0, (2, 2)), alpha=0.65, shrinkA=17, shrinkB=17, connectionstyle="arc3,rad=-0.55")) ax.text(2.55, 0.95, "geri çekil\n(yığın boşalır)", ha="center", va="center", fontsize=7.5, color=COL_SLATE_500, style="italic", zorder=6) ax.add_patch(FancyArrowPatch( (2.55, 0.62), (2.18, 0.18), arrowstyle="-|>", mutation_scale=9, color=COL_SLATE_500, linewidth=1.1, zorder=3, linestyle=(0, (2, 2)), alpha=0.7, connectionstyle="arc3,rad=-0.3")) ax.text(0.85, 2.78, "DFS — derinlemesine arama (dibe dal)", ha="center", va="center", fontsize=11.5, color=COL_TEXT, weight="bold", zorder=6) ax.text(0.85, -0.78, "derine in: bir düğümden EN UZAĞA dal\n" "tıkanınca geri çekil (ataya dön — özyineleme yığını)", ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6) ax.set_xlim(-1.05, 3.15) ax.set_ylim(-1.15, 3.05) ax.set_aspect("equal") ax.axis("off") # ---- motor verisi + ASSERT (figür yalnız bunu çizer) ---- _bvd_g = build_example_graph() _bvd_src = "a" _bvd_levels = bfs_levels(_bvd_g, _bvd_src) _bvd_order = dfs_visit_order(_bvd_g, _bvd_src)["order"] assert _bvd_levels == [["a"], ["b", "c"], ["d", "e"], ["f"], ["g"]], _bvd_levels assert _bvd_order == ["a", "b", "d", "c", "e", "f", "g"], _bvd_order assert _bvd_levels[1] == ["b", "c"] # BFS: b,c aynı katman assert _bvd_order[1] == "b" and _bvd_order[2] == "d" # DFS: b'den hemen d'ye assert _bvd_order[3] == "c" # c'ye 4. sırada varır fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.0, 6.2)) fig.patch.set_facecolor(COL_WHITE) _bvd_bfs_panel(axL, _bvd_levels, _bvd_src) _bvd_dfs_panel(axR, _bvd_order, _bvd_src) fig.suptitle( "İki arama stratejisi — AYNI çizge: BFS dalga dalga · DFS dibe dalar", color=COL_TEXT, fontsize=13.5, weight="bold", y=0.985) fig.text(0.5, 0.045, "BFS = en kısa yol (ağırlıksız çizge) | " "DFS = yapısal sorular (DAG mı? · bağlı bileşenler · topolojik sıra · çevrim)" " · (Solomon 6:55)", ha="center", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", style="italic") fig.subplots_adjust(top=0.90, bottom=0.115, left=0.02, right=0.98, wspace=0.04) plt.show() ``` ## 2. Erişilebilirlik Problemi ve Ebeveyn Ağacı {#sec-2-erisilebilirlik-ebeveyn-agaci} **Erişilebilirlik (reachability):** bir kaynak $s$'den yönlü kenarları izleyerek **hangi düğümlere ulaşılır?** > *"the reachability problem is just asking, which nodes can I reach from a given source?"* — Solomon, 8:20 BFS ile çözülebilir (erişilemeyen düğümün mesafesi $\infty$), ama daha doğrudan bir yol var. "Kanıt" istersek (sadece "ulaşılır" değil, "nasıl"), her düğümü **öncülü (predecessor)** $P(v)$ ile etiketleriz — kaynaktan o düğüme giden *bir* yolda önceki düğüm. Yolu, $P$'yi geriye izleyip listeyi ters çevirerek kurarız. Önemli fark (Ders 13'ün en kısa yol ağacından): buradaki **ebeveyn ağacı** en kısa yolu garanti etmez — erişilebilirlikte yolun kısalığı umurumuzda değil, sadece varlığı. Yine de bir ağaçtır (çevrim olamaz). ## 3. DFS Algoritması {#sec-3-dfs-algoritmasi} DFS özyinelemeli bir `visit` fonksiyonudur: kaynağı işaretle; her komşu $v$ için, **henüz ziyaret edilmemişse** ($P(v) = \text{None}$) ebeveynini "ben" yap ve özyinelemeli olarak ona in. **Çalışılan Örnek — gezinme sırası.** Kaynak 1'den başla. 1'in tek komşusu 2 → visit(2). 2'nin komşuları 3 ve 5; önce 3 → visit(3) → visit(4). Özyineleme dibe vurdu, geri çekil. 2 sonraki komşusu 5'e iner → visit(5). Sıra: $1 \to 2 \to 3 \to 4 \to (\text{geri}) \to 5$. Dikkat: bu **seviye kümelerini izlemez** — DFS dibe (4) gidip sonra 2'ye geri sarıp 5'i çağırdı. "Geri çekilme" = özyinelemenin çözülmesi. ```python def dfs(adj, s, parent=None): if parent is None: parent = {s: None} # kaynagi ziyaret et for v in adj[s]: if v not in parent: # henuz ziyaret edilmemis parent[v] = s # ebeveyni = ben dfs(adj, v, parent) # ozyinele return parent ``` @fig-dfs-run bu çalışılan örneği adım adım izler: üstte yönlü çizge ($1 \to 2 \to 3 \to 4$ dibe in, sonra geri çekilip 5'e dal), altta olay şeridi — in/out olaylarının sırası, $\text{out}(4), \text{out}(3)$ olaylarının $\text{in}(5)$'ten **önce** gelmesi (dibe vur, geri sar, sonra 5). ```{python} #| label: fig-dfs-run #| fig-cap: "DFS çalışılan örnek: 1→2→3→4 dibe in, sonra geri çekilip 5'e dal (L10 §3, İMZA figür). ÜST: yönlü çizge — kenarlar 1→2, 2→3, 2→5, 3→4. Ziyaret (ileri) okları AMBER + sıra numarası: 1→2 [1], 2→3 [2], 3→4 [3], sonra 2→5 [4]. Geri-çekilme okları KESİKLİ GRİ: 4→3, 3→2 (özyineleme çözülmesi; 5 ziyaretinden ÖNCE). ALT: olay şeridi — in(1) in(2) in(3) in(4) out(4) out(3) in(5) out(5) out(2) out(1); 'in' amber dolu, 'out' soluk çerçeve. out(4) ve out(3), in(5)'ten ÖNCE: dibe vur (4), geri sar (out 4,3), sonra 5. Seviye kümeleri İZLENMEZ — geri çekilme = özyinelemenin çözülmesi (out'lar in'lerin TERSİ sırada kapanır). Veri MOTORDAN: dfs_visit_order(build_dfs_example(),1)['order']=[1,2,3,4,5]; events=[in1,in2,in3,in4,out4,out3,in5,out5,out2,out1] (Solomon L10 §3)." #| fig-width: 11.0 #| fig-height: 7.0 # fig-dfs-run (L10 §3 İMZA): DFS çalışılan örnek + olay şeridi (in/out). # Veri MOTORDAN (dfs_visit_order / build_dfs_example). networkx YOK — elle koordinat. _DR_POS = {1: (0.0, 1.0), 2: (1.4, 1.0), 3: (2.8, 1.9), 4: (4.2, 1.9), 5: (2.8, 0.1)} _DR_NODE_R = 0.26 _DR_FORWARD = [(1, 2, 1), (2, 3, 2), (3, 4, 3), (2, 5, 4)] _DR_BACKTRACK = [(4, 3), (3, 2)] def _dr_node(ax, node, is_source=False): x, y = _DR_POS[node] ax.add_patch(Circle((x, y), _DR_NODE_R, facecolor=COL_AMBER_100 if is_source else COL_BG, edgecolor=COL_ACCENT if is_source else COL_PRIMARY, linewidth=3.0 if is_source else 1.9, zorder=5, clip_on=False)) ax.text(x, y, str(node), ha="center", va="center", fontsize=13, color=COL_AMBER_700 if is_source else COL_TEXT, weight="bold", zorder=6) def _dr_graph(ax): for u, v, order_no in _DR_FORWARD: x0, y0 = _DR_POS[u] x1, y1 = _DR_POS[v] ax.add_patch(FancyArrowPatch( (x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=18, color=COL_ACCENT, linewidth=2.6, zorder=3, shrinkA=_DR_NODE_R * 60, shrinkB=_DR_NODE_R * 60)) mx, my = (x0 + x1) * 0.5, (y0 + y1) * 0.5 off_x = 0.16 if (u, v) == (2, 5) else 0.0 off_y = 0.18 if (u, v) in ((1, 2),) else 0.16 ax.add_patch(Circle((mx + off_x, my + off_y), 0.155, facecolor=COL_WHITE, edgecolor=COL_ACCENT, linewidth=1.8, zorder=4)) ax.text(mx + off_x, my + off_y, str(order_no), ha="center", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=5) for u, v in _DR_BACKTRACK: x0, y0 = _DR_POS[u] x1, y1 = _DR_POS[v] ax.add_patch(FancyArrowPatch( (x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=14, color=COL_SLATE_400, linewidth=1.8, linestyle=(0, (4, 3)), zorder=2, shrinkA=_DR_NODE_R * 60, shrinkB=_DR_NODE_R * 60, connectionstyle="arc3,rad=0.28")) for node in _DR_POS: _dr_node(ax, node, is_source=(node == 1)) sx, sy = _DR_POS[1] ax.text(sx, sy + _DR_NODE_R + 0.22, "kaynak", ha="center", va="bottom", fontsize=9, color=COL_AMBER_700, weight="bold", style="italic", zorder=6) lx, ly = 3.45, 0.55 ax.add_patch(FancyArrowPatch((lx, ly + 0.30), (lx + 0.55, ly + 0.30), arrowstyle="-|>", mutation_scale=14, color=COL_ACCENT, linewidth=2.4, zorder=4)) ax.text(lx + 0.68, ly + 0.30, "ileri (in) — özyinelemeye dal", ha="left", va="center", fontsize=8.2, color=COL_AMBER_700, weight="bold", zorder=5) ax.add_patch(FancyArrowPatch((lx, ly), (lx + 0.55, ly), arrowstyle="-|>", mutation_scale=12, color=COL_SLATE_400, linewidth=1.8, linestyle=(0, (4, 3)), zorder=4)) ax.text(lx + 0.68, ly, "geri çekilme (out) — özyineleme çözülmesi", ha="left", va="center", fontsize=8.2, color=COL_SLATE_500, zorder=5) def _dr_event_strip(ax, events): n = len(events) cell_w, cell_h = 0.96, 0.66 x0, y = 0.10, 0.0 ax.text(x0, y + cell_h + 0.30, "olay dizisi (özyineleme zaman ekseni — soldan sağa)", ha="left", va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=6) for k, (kind, v) in enumerate(events): x = x0 + k * cell_w is_in = (kind == "in") fc, ec, lw, tcol = ((COL_AMBER_100, COL_ACCENT, 2.4, COL_AMBER_700) if is_in else (COL_WHITE, COL_SLATE_400, 1.4, COL_SLATE_500)) ax.add_patch(FancyBboxPatch( (x, y), cell_w * 0.9, cell_h, boxstyle="round,pad=0.02,rounding_size=0.06", fc=fc, ec=ec, linewidth=lw, zorder=3)) ax.text(x + cell_w * 0.45, y + cell_h * 0.5, f"{kind}({v})", ha="center", va="center", fontsize=9.5, color=tcol, weight="bold", zorder=5) ax.text(x + cell_w * 0.45, y - 0.20, str(k + 1), ha="center", va="center", fontsize=7.5, color=COL_SLATE_500, zorder=4) x_in4 = x0 + 3 * cell_w + cell_w * 0.45 ax.text(x_in4, y + cell_h + 0.06, "dibe vur (4)", ha="center", va="bottom", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6) x_ot4 = x0 + 4 * cell_w x_ot3 = x0 + 6 * cell_w - cell_w * 0.1 yb = y + cell_h + 0.08 ax.plot([x_ot4 + 0.05, x_ot3], [yb, yb], color=COL_SLATE_500, linewidth=1.4, zorder=4) ax.plot([x_ot4 + 0.05, x_ot4 + 0.05], [yb, yb - 0.10], color=COL_SLATE_500, linewidth=1.4, zorder=4) ax.plot([x_ot3, x_ot3], [yb, yb - 0.10], color=COL_SLATE_500, linewidth=1.4, zorder=4) ax.text((x_ot4 + x_ot3) * 0.5 + 0.02, yb + 0.04, "geri sar (out 4,3)", ha="center", va="bottom", fontsize=8, color=COL_SLATE_500, zorder=6) x_in5 = x0 + 6 * cell_w + cell_w * 0.45 ax.annotate("sonra 5", xy=(x_in5, y + cell_h), xytext=(x_in5, y + cell_h + 0.42), ha="center", va="bottom", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6, arrowprops=dict(arrowstyle="-|>", color=COL_ACCENT, linewidth=1.8)) return x0, cell_w, n # ---- motor verisi + ASSERT (figür yalnız bunu çizer) ---- _dr_adj = build_dfs_example() _dr_tr = dfs_visit_order(_dr_adj, 1) _dr_order = _dr_tr["order"] _dr_events = _dr_tr["events"] assert _dr_order == [1, 2, 3, 4, 5], _dr_order assert _dr_events == [("in", 1), ("in", 2), ("in", 3), ("in", 4), ("out", 4), ("out", 3), ("in", 5), ("out", 5), ("out", 2), ("out", 1)], _dr_events assert (_dr_events.index(("out", 4)) < _dr_events.index(("in", 5)) and _dr_events.index(("out", 3)) < _dr_events.index(("in", 5))) fig, (ax_g, ax_e) = plt.subplots(2, 1, figsize=(11.0, 7.0), gridspec_kw={"height_ratios": [1.55, 1.0]}) fig.patch.set_facecolor(COL_WHITE) _dr_graph(ax_g) ax_g.set_xlim(-0.7, 6.6) ax_g.set_ylim(-0.45, 2.65) ax_g.set_aspect("equal") ax_g.axis("off") ax_g.set_title( "DFS çalışılan örnek: 1→2→3→4 dibe in, sonra geri çekilip 5'e dal (Solomon L10 §3)", color=COL_TEXT, fontsize=12.5, weight="bold", pad=8) _dr_x0, _dr_cw, _dr_n = _dr_event_strip(ax_e, _dr_events) ax_e.set_xlim(-0.25, _dr_x0 + _dr_n * _dr_cw + 0.30) ax_e.set_ylim(-0.55, 1.40) ax_e.set_aspect("equal") ax_e.axis("off") fig.text(0.5, 0.025, "seviye kümeleri İZLENMEZ — dibe vur (4), geri sar, sonra 5 · " "geri çekilme = özyinelemenin çözülmesi (out, in'lerin TERSİ sırada kapanır)", ha="center", va="center", fontsize=8.6, color=COL_SLATE_500, style="italic") fig.subplots_adjust(left=0.03, right=0.97, top=0.92, bottom=0.08, hspace=0.18) plt.show() ``` ## 4. DFS Doğruluğu {#sec-4-dfs-dogrulugu} **İddia:** DFS, erişilebilir her $v$'yi ziyaret eder ve ebeveynini doğru atar. **Çalışılan Örnek — kaynağa uzaklık üzerinden tümevarım.** Kaynağa uzaklık $k$ üzerinden tümevarım. - **Temel ($k = 0$):** uzaklık 0 olan tek düğüm kaynağın kendisidir; algoritma ilk satırda onu doğru kurar. ✓ - **Adım ($k \to k+1$):** $v$, kaynaktan uzaklık $k+1$ olsun. En kısa yolda $v$'den bir önceki düğüm $u$'nun uzaklığı $k$'dır → tümevarım varsayımıyla $u$ doğru ziyaret edilir. visit($u$) çağrıldığında, $v \in \text{Adj}^{+}(u)$ olduğundan DFS $v$'yi değerlendirir. İki durum: ya $P(v) \neq \text{None}$ (zaten uygun bir ebeveyn bulunmuş) ya da $P(v) = \text{None}$ (bir sonraki satır ebeveyni doğru atar). Her iki durumda da $v$'nin ebeveyni doğru. ✓ Sezgisel olarak basit; biçimsel tümevarım totoloji gibi hissettirebilir ama değil. ## 5. DFS Çalışma Süresi O(E) {#sec-5-dfs-calisma-suresi} Her düğüm en fazla bir kez ziyaret edilir (visit her düğüm için bir kez çağrılır); her kenar en fazla bir kez gezilir (kenarın "çıkış" düğümü bir kez ziyaret edildiğinden). Önemli ayrım: BFS, başta $O(V)$ yer ayırdığı için $O(V + E)$'dir; DFS ise yalnızca **erişilebilir** kenarlara dokunur, hiç erişilemeyen düğümü görmez → $O(E)$. > *"depth-first search... it just takes order e time."* — Solomon, 22:09 (Kenarsız bir çizgede BFS yine $O(V)$, DFS ise $O(E) = O(0)$ işi yapar; sınırlar birebir aynı değildir.) ## 6. DFS En Kısa Yol Vermez {#sec-6-dfs-en-kisa-yol-vermez} DFS'in ürettiği yol **en kısa olmak zorunda değildir**. > *"there's no reason why the path that we get should be the shortest."* — Solomon, 24:01 Uç örnek: bir **çevrim çizgesi** (büyük halka). Kaynaktan başlayıp komşu komşuyu özyinelemeli çağırırsak, son düğüme 4 düğümlük bir zincirin arkasından varırız — oysa tek bir kenarla doğrudan gidilebilirdi. DFS o kenarı *seçmedi*. Bu yüzden ağırlıksız en kısa yol için **BFS** kullanılır; DFS yapısal sorular içindir. ## 7. Bağlılık ve Bağlı Bileşenler {#sec-7-baglilik-ve-bagli-bilesenler} Bir çizge **bağlı (connected)** ise her düğümden her düğüme bir yol vardır. > *"a graph is connected if there's a path getting from every vertex to every other vertex."* — Solomon, 25:14 Yönlü çizgede bağlılık tuhaftır ($u \to v$ var ama $v \to u$ yok olabilir), bu yüzden çoğunlukla **yönsüz** çizgelerde konuşulur: düğümler "kümeler" hâlinde gelir — bir **bağlı bileşen (connected component)**. **Bağlı bileşenler problemi:** tüm kümeleri listele. Çözüm **full DFS**: tüm düğümler üzerinde bir döngü; düğüm henüz ziyaret edilmemişse ondan DFS başlat (o bileşeni "flood fill" eder), topla, devam et. Her kenar en fazla bir kez gezilir (bir düğüm iki bileşende olamaz) → $O(V + E)$. ```python def full_dfs(adj, V): parent = {} components = [] for s in V: # tum dugumler uzerinde dongu if s not in parent: # yeni bilesen parent[s] = None dfs(adj, s, parent) components.append(s) # bu bilesenin temsilcisi return components, parent ``` @fig-components full DFS'i "ada keşfi" olarak gösterir: üç bağlı bileşen ($\{1,2,3\}$, $\{4,5\}$, $\{6\}$), her birinin temsilci kökü ($1, 4, 6$), ve altta dış-döngünün düğümleri sırayla tarayışı (ziyaretsiz köke yeni DFS başlat, görülmüşü atla). ```{python} #| label: fig-components #| fig-cap: "Full DFS = bağlı bileşenler: ziyaretsiz her köke yeni DFS başlat (ada ada) (L10 §7, İMZA figür). ÜST: 3 ada çizgesi — küme 1 {1,2,3} (üçgen-vari, amber halo, bileşen C₁), küme 2 {4,5} (çift, slate halo, C₂), küme 3 {6} (tek düğüm, beyaz halo, C₃); her ada altında bileşen etiketi. Temsilci kökler (her bileşenin ilk ziyaret edilen düğümü) amber dolgulu + 'kök' etiketi: 1, 4, 6. ALT: full DFS dış-döngü şeridi — düğümler 1..6 SIRAYLA taranır; 1 ziyaretsiz → DFS başlat (ada 1'i sular), 2,3 görülmüş → atla, 4 ziyaretsiz → DFS başlat (ada 2), 5 atla, 6 ziyaretsiz → DFS başlat (ada 3); amber 'DFS' rozeti her başlatmada. Dış döngü her düğüme 1 kez bakar + her kenar en fazla 1 kez gezilir → O(V+E). Veri MOTORDAN: connected_components=[[1,2,3],[4,5],[6]]; full_dfs temsilcileri=[1,4,6] (Solomon L10 §7)." #| fig-width: 10.5 #| fig-height: 6.5 # fig-components (L10 §7 İMZA): full DFS → bağlı bileşenler (3 ada). # Veri MOTORDAN (make_undirected / connected_components / full_dfs). networkx YOK. _CMP_POS = { 1: (0.35, 1.05), 2: (1.45, 1.55), 3: (1.45, 0.55), # ada 1 4: (3.55, 1.45), 5: (4.65, 0.65), # ada 2 6: (6.40, 1.05), # ada 3 } _CMP_EDGES = [(1, 2), (2, 3), (4, 5)] _CMP_R = 0.26 _CMP_HALO = [ (COL_AMBER_100, COL_ACCENT, COL_AMBER_700), (COL_BG, COL_SLATE_500, COL_SLATE_500), (COL_WHITE, COL_SLATE_400, COL_SLATE_500), ] def _cmp_halo(members): xs = [_CMP_POS[v][0] for v in members] ys = [_CMP_POS[v][1] for v in members] cx = (min(xs) + max(xs)) / 2.0 cy = (min(ys) + max(ys)) / 2.0 rx = (max(xs) - min(xs)) / 2.0 + _CMP_R + 0.34 ry = (max(ys) - min(ys)) / 2.0 + _CMP_R + 0.34 return cx, cy, 2 * rx, 2 * ry # ---- motor verisi + ASSERT (figür yalnız bunu çizer) ---- _cmp_ug = make_undirected([(1, 2), (2, 3), (4, 5)]) _cmp_ug.setdefault(6, []) _cmp_comps = connected_components(_cmp_ug) _cmp_parent, _cmp_reps = full_dfs(_cmp_ug) assert _cmp_comps == [[1, 2, 3], [4, 5], [6]], _cmp_comps assert _cmp_reps == [1, 4, 6], _cmp_reps _cmp_comp_of = {v: ci for ci, members in enumerate(_cmp_comps) for v in members} _cmp_rep_set = set(_cmp_reps) fig, ax = plt.subplots(figsize=(10.5, 6.5)) fig.patch.set_facecolor(COL_WHITE) for ci, members in enumerate(_cmp_comps): cx, cy, w, h = _cmp_halo(members) fc, ec, _tc = _CMP_HALO[ci] ax.add_patch(Ellipse((cx, cy), w, h, facecolor=fc, edgecolor=ec, linewidth=2.0, linestyle=(0, (5, 3)), alpha=0.55, zorder=0)) ax.text(cx, cy + h / 2 + 0.14, f"C{ci + 1} = {{{', '.join(str(v) for v in members)}}}", ha="center", va="bottom", fontsize=9.5, color=_CMP_HALO[ci][2], weight="bold", zorder=6) for u, v in _CMP_EDGES: x0, y0 = _CMP_POS[u] x1, y1 = _CMP_POS[v] ax.plot([x0, x1], [y0, y1], color=COL_SLATE_400, linewidth=1.8, zorder=2, solid_capstyle="round") for v, (x, y) in _CMP_POS.items(): is_rep = v in _cmp_rep_set fc, ec, tcol, lw = ((COL_ACCENT, COL_AMBER_700, COL_WHITE, 3.0) if is_rep else (COL_BG, COL_PRIMARY, COL_TEXT, 2.0)) ax.add_patch(Circle((x, y), _CMP_R, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=5)) ax.text(x, y, str(v), ha="center", va="center", fontsize=13, color=tcol, weight="bold", zorder=6) if is_rep: ax.text(x, y + _CMP_R + 0.16, "kök", ha="center", va="bottom", fontsize=7.5, color=COL_AMBER_700, weight="bold", style="italic", zorder=6) ax.text(3.4, 2.92, "FULL DFS → bağlı bileşenler: her ada bir DFS ağacıyla taranır", ha="center", va="center", fontsize=10, color=COL_PRIMARY, weight="bold", zorder=6) _cmp_strip_y, _cmp_cell_w, _cmp_x0 = -1.15, 1.05, 0.30 _cmp_order = list(_cmp_ug.keys()) assert _cmp_order == [1, 2, 3, 4, 5, 6], _cmp_order _cmp_seen = set() for k, v in enumerate(_cmp_order): cx = _cmp_x0 + k * _cmp_cell_w if v not in _cmp_seen: start = True for m in _cmp_comps[_cmp_comp_of[v]]: _cmp_seen.add(m) fc, ec, tcol, lw = COL_ACCENT, COL_AMBER_700, COL_WHITE, 2.6 else: start = False fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_400, 1.4 ax.add_patch(Circle((cx, _cmp_strip_y), 0.24, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=5)) ax.text(cx, _cmp_strip_y, str(v), ha="center", va="center", fontsize=11.5, color=tcol, weight="bold", zorder=6) if start: ax.add_patch(FancyBboxPatch( (cx - 0.30, _cmp_strip_y + 0.34), 0.60, 0.26, boxstyle="round,pad=0.02,rounding_size=0.06", fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.6, zorder=5)) ax.text(cx, _cmp_strip_y + 0.47, "DFS", ha="center", va="center", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6) ax.text(cx, _cmp_strip_y - 0.40, "ziyaretsiz\n→ başlat", ha="center", va="top", fontsize=7, color=COL_AMBER_700, weight="bold", zorder=6) else: ax.text(cx, _cmp_strip_y - 0.40, "görülmüş\n→ atla", ha="center", va="top", fontsize=7, color=COL_SLATE_400, style="italic", zorder=6) ax.text(_cmp_x0 - 0.05, _cmp_strip_y + 0.75, "dış döngü (düğüm 1..6 sırayla):", ha="left", va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=6) ax.text(_cmp_x0 + len(_cmp_order) * _cmp_cell_w + 0.05, _cmp_strip_y, f"temsilciler: {_cmp_reps}", ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", family="monospace", zorder=6) fig.suptitle( "Full DFS = bağlı bileşenler: ziyaretsiz her köke yeni DFS başlat (ada ada)", color=COL_TEXT, fontsize=13, weight="bold", y=0.975) ax.text(3.4, -2.35, "dış döngü her düğüme 1 kez bakar + her kenar en fazla 1 kez gezilir → O(V + E)" " · (Solomon L10 §7)", ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6) ax.set_xlim(-0.35, 7.30) ax.set_ylim(-2.70, 3.25) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ## 8. Yönlü Çevrimsiz Çizge (DAG) ve Topolojik Sıralama {#sec-8-dag-topolojik-siralama} Bir **DAG (Directed Acyclic Graph)**: yönlü kenarlı, **çevrimsiz** çizge. (Yönlendirilmiş bir ağaç bir DAG örneğidir.) > *"a DAG is a Directed Acyclic Graph."* — Solomon, 32:28 **Topolojik sıralama:** her düğüme bir sıra indeksi $f$ atayan, şu özelliği sağlayan bir düzen: her $u \to v$ kenarı için $f(u) < f(v)$ ($u$, $v$'den önce gelir). > *"if I have a directed edge from u to v, then f of u is less than f of v."* — Solomon, 34:46 Topolojik sıralama **benzersiz değildir** — $A \to B$, $A \to C$, $B \to D$, $C \to D$ çizgesinde hem "A C B D" hem "A B C D" geçerlidir. Bu "özgürlük", algoritmanın çoktan birini bulmasına izin verir. ## 9. Bitiş Sırası → Topolojik Sıralama {#sec-9-bitis-sirasi-topolojik} **Bitiş sırası (finishing order):** full DFS çalıştır; bir düğümün visit çağrısı **tamamlandığında** (tüm komşuları gezildiğinde) onu sıraya ekle. **İddia:** bir DAG'da, **bitiş sırasının tersi** geçerli bir topolojik sıralamadır. > *"the reverse of the finishing order is a topological order."* — Solomon, 37:54 **Çalışılan Örnek — kanıt (iki durum).** Bir $u \to v$ kenarı al; ters bitiş sırasında $u$'nun $v$'den önce geldiğini göstermeliyiz. - **Durum 1 — $u$, $v$'den önce ziyaret edildi:** visit($u$), $v$'yi (henüz ziyaretsizse) çağırır; visit($v$), visit($u$)'dan **önce tamamlanır**. Ters sırada bu, $u$'yu $v$'nin önüne koyar. ✓ - **Durum 2 — $v$, $u$'dan önce ziyaret edildi:** çizge çevrimsiz olduğundan $v$'den $u$'ya yol **yoktur** (olsaydı çevrim olurdu). O hâlde visit($v$), $u$'yu hiç görmeden tamamlanır → Durum 1'le aynı sonuç: ters sırada $u$, $v$'den önce. ✓ @fig-topo-order bu mekanizmayı gösterir: örnek DAG, full DFS'in **bitiş sırası** $[D, B, C, A]$ (D yaprak, ilk biter; A kök, son biter), ve onun **tersi** = topolojik sıra $[A, C, B, D]$; her DAG kenarı için $f(u) < f(v)$ onayı yeşil rozetle, ve "benzersiz değil" notu ($[A, B, C, D]$ de geçerli). ```{python} #| label: fig-topo-order #| fig-cap: "DAG'da topolojik sıra = TERS bitiş sırası (tek DFS geçişi, O(V+E)) (L10 §8-9, İMZA figür). ÜST-SOL: örnek DAG — A üstte, B ve C ortada yan yana, D altta (elmas); yönlü oklar A→B, A→C, B→D, C→D. ORTA serit: BİTİŞ SIRASI (visit tamamlanınca out() ile eklenir) [D, B, C, A]; D ilk biter (yaprak), A son biter (kök). 'TERSE ÇEVİR' dönüş oku. ALT serit: TOPOLOJİK SIRA = ters bitiş = [A, C, B, D] (amber kutular); her DAG kenarı için f(u)<f(v) onayı yeşil ✓ rozeti (A<C, A<B, B<D, C<D); verify_topological=True. YAN NOT: topolojik sıra BENZERSİZ DEĞİL — [A, C, B, D] ve [A, B, C, D] ikisi de geçerli (B-C arası kenar yok); ters bitiş bunlardan BİRİNİ bulur. Kanıt iki durum (Solomon 37:54). Veri MOTORDAN: build_dag_example={A:[B,C],B:[D],C:[D],D:[]}; finishing_order=[D,B,C,A]; topological_order=[A,C,B,D]; verify=True." #| fig-width: 11.0 #| fig-height: 7.0 # fig-topo-order (L10 §8-9 İMZA): ters bitiş sırası = topolojik sıra. # Veri MOTORDAN (build_dag_example / finishing_order / topological_order / # verify_topological). networkx YOK — elle koordinat. _TO_POS = {"A": (1.50, 2.60), "B": (0.70, 1.40), "C": (2.30, 1.40), "D": (1.50, 0.20)} _TO_DAG_EDGES = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")] _TO_R = 0.30 _TO_COL_OK = "#3f7d5e" _TO_COL_OK_BG = "#cfe8da" def _to_draw_dag(ax): for u, v in _TO_DAG_EDGES: ux, uy = _TO_POS[u] vx, vy = _TO_POS[v] ax.add_patch(FancyArrowPatch( (ux, uy), (vx, vy), arrowstyle="-|>", mutation_scale=16, color=COL_SLATE_500, linewidth=2.0, shrinkA=_TO_R * 62, shrinkB=_TO_R * 62, zorder=2)) for v, (x, y) in _TO_POS.items(): ax.add_patch(Circle((x, y), _TO_R, facecolor=COL_BG, edgecolor=COL_PRIMARY, linewidth=2.2, zorder=5)) ax.text(x, y, v, ha="center", va="center", fontsize=15, color=COL_TEXT, weight="bold", zorder=6) ax.text(1.50, 3.30, "DAG (yönlü çevrimsiz çizge)", ha="center", va="center", fontsize=11, color=COL_PRIMARY, weight="bold", zorder=6) ax.text(1.50, -0.42, "kenarlar: A→B, A→C, B→D, C→D", ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=6) def _to_draw_strip(ax, x0, y, seq, fill, edge, tcol, prefix_label): cell_w, cell_h = 0.92, 0.78 centers = {} for k, node in enumerate(seq): x = x0 + k * (cell_w + 0.22) ax.add_patch(FancyBboxPatch( (x, y), cell_w, cell_h, boxstyle="round,pad=0.02,rounding_size=0.08", fc=fill, ec=edge, linewidth=2.4, zorder=4)) cx, cy = x + cell_w * 0.5, y + cell_h * 0.5 centers[node] = (cx, cy) ax.text(cx, cy, node, ha="center", va="center", fontsize=14, color=tcol, weight="bold", zorder=5) ax.text(cx, y + cell_h + 0.13, f"{prefix_label}{k + 1}", ha="center", va="center", fontsize=7.5, color=COL_SLATE_500, weight="bold", zorder=5) if k < len(seq) - 1: ax.add_patch(FancyArrowPatch( (x + cell_w, cy), (x + cell_w + 0.22, cy), arrowstyle="-|>", mutation_scale=11, color=edge, linewidth=1.6, zorder=4)) return centers, cell_w, cell_h # ---- motor verisi + ASSERT (figür yalnız bunu çizer) ---- _to_dag = build_dag_example() _to_fin = finishing_order(_to_dag) _to_topo = topological_order(_to_dag) _to_ok = verify_topological(_to_dag, _to_topo) assert _to_dag == {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}, _to_dag assert _to_fin == ["D", "B", "C", "A"], _to_fin assert _to_topo == ["A", "C", "B", "D"], _to_topo assert _to_ok is True and list(reversed(_to_fin)) == _to_topo fig, ax = plt.subplots(figsize=(11.0, 7.0)) fig.patch.set_facecolor(COL_WHITE) _to_draw_dag(ax) _to_mid_x0, _to_mid_y = 5.0, 2.05 ax.text(_to_mid_x0 - 0.30, _to_mid_y + 1.18, "BİTİŞ SIRASI (visit tamamlanınca eklenir — out())", ha="left", va="center", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=6) _to_draw_strip(ax, _to_mid_x0, _to_mid_y, _to_fin, fill=COL_BG, edge=COL_PRIMARY, tcol=COL_TEXT, prefix_label="bitiş ") ax.text(_to_mid_x0 + 4.30, _to_mid_y + 0.39, "D ilk biter (yaprak)\nA son biter (kök)", ha="left", va="center", fontsize=7.5, color=COL_SLATE_500, style="italic", zorder=6) _to_rev_x = _to_mid_x0 + 4.55 ax.add_patch(FancyArrowPatch( (_to_rev_x, _to_mid_y - 0.06), (_to_rev_x, _to_mid_y - 1.10), arrowstyle="-|>", mutation_scale=18, color=COL_AMBER_600, linewidth=2.6, zorder=6)) ax.text(_to_rev_x + 0.18, _to_mid_y - 0.58, "TERSE\nÇEVİR", ha="left", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", style="italic", zorder=6) _to_bot_x0, _to_bot_y = 5.0, 0.55 ax.text(_to_bot_x0 - 0.30, _to_bot_y + 1.18, "TOPOLOJİK SIRA = ters bitiş sırası", ha="left", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=6) _to_draw_strip(ax, _to_bot_x0, _to_bot_y, _to_topo, fill=COL_AMBER_100, edge=COL_ACCENT, tcol=COL_AMBER_700, prefix_label="sıra ") _to_f = {v: i for i, v in enumerate(_to_topo)} _to_badge_y = _to_bot_y - 0.52 _to_badge_x0, _to_badge_w = _to_bot_x0 + 0.05, 1.18 for k, (u, v) in enumerate(_TO_DAG_EDGES): assert _to_f[u] < _to_f[v], (u, v, _to_f) bx = _to_badge_x0 + k * _to_badge_w ax.add_patch(FancyBboxPatch( (bx, _to_badge_y - 0.16), _to_badge_w * 0.92, 0.34, boxstyle="round,pad=0.02,rounding_size=0.06", fc=_TO_COL_OK_BG, ec=_TO_COL_OK, linewidth=1.6, zorder=4)) ax.text(bx + _to_badge_w * 0.46, _to_badge_y, f"✓ f({u})<f({v})", ha="center", va="center", fontsize=8.5, color=_TO_COL_OK, weight="bold", zorder=5) ax.text(_to_bot_x0 - 0.30, _to_badge_y - 0.50, f"verify_topological(dag, sıra) = {_to_ok} — her kenar soldan sağa akar", ha="left", va="center", fontsize=8.5, color=_TO_COL_OK, weight="bold", zorder=6) _to_note_x, _to_note_y, _to_note_w, _to_note_h = 5.0, -1.55, 6.05, 0.92 ax.add_patch(FancyBboxPatch( (_to_note_x, _to_note_y), _to_note_w, _to_note_h, boxstyle="round,pad=0.05,rounding_size=0.10", fc=COL_BG, ec=COL_SLATE_400, linewidth=1.6, zorder=3)) ax.text(_to_note_x + 0.20, _to_note_y + _to_note_h - 0.26, "topolojik sıra BENZERSİZ DEĞİL", ha="left", va="center", fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5) ax.text(_to_note_x + 0.20, _to_note_y + _to_note_h - 0.56, "[A, C, B, D] ve [A, B, C, D] ikisi de geçerli (B ile C arası kenar yok)", ha="left", va="center", fontsize=8.8, color=COL_SLATE_500, zorder=5) ax.text(_to_note_x + 0.20, _to_note_y + 0.20, "ters bitiş sırası bu geçerli sıralamalardan BİRİNİ bulur", ha="left", va="center", fontsize=8.8, color=COL_AMBER_700, style="italic", weight="bold", zorder=5) fig.suptitle( "DAG'da topolojik sıra = TERS bitiş sırası (tek DFS geçişi, O(V+E))", color=COL_TEXT, fontsize=13, weight="bold", y=0.975) ax.text(0.06, -1.95, "u→v kenarı için u, v'den DAHA SONRA biter (v u'nun torunudur ya da " "ayrık) → terse çevirince f(u) < f(v): iki durum kanıtı (Solomon 37:54)", ha="left", va="center", fontsize=8.4, color=COL_SLATE_500, style="italic", zorder=6) ax.set_xlim(-0.2, 11.4) ax.set_ylim(-2.25, 3.65) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ## 10. Çevrim Tespiti {#sec-10-cevrim-tespiti} DAG değilsek topolojik sıralama elde edemeyiz. Yani: ters bitiş sırasını hesapla, sonra her kenarın $f(u) < f(v)$ ilişkisine uyup uymadığını kontrol et. **Uymayan bir kenar bulursak çizge DAG değildir → bir çevrim vardır.** (Aslında: topolojik sıralama var $\iff$ çizge DAG.) Çevrimi yalnızca tespit değil **bulmak** için: $G$ çevrim içeriyorsa, full DFS bir $v$ düğümünden onun bir **atasına (ancestor)** giden bir kenar gezer (atası = özyineleme ağacında $v$'den önce gelen düğüm). > *"full DFS will traverse an edge from a vertex v to some ancestor of v."* — Solomon, 48:20 Kanıt taslağı: çevrim $v_0 \to v_1 \to \ldots \to v_k \to v_0$ olsun; $v_0$'ı DFS'in ilk gördüğü düğüm seç. $v_0$'ın özyineleme ağacı tamamlanmadan, ondan erişilebilen $v_1, \ldots, v_k$ de tamamlanır; $v_k$ komşularını gezerken $v_0$ kenarını görür — bu, $v_k$'den atası $v_0$'a giden **geri kenardır (back edge)**. DFS sırasında bu geri kenarı yakaladığın an çevrimi bulmuş olursun. @fig-cycle-detect bu ayrımı iki panelle gösterir: solda çevrimli çizge ($1 \to 2 \to 3 \to 1$ + $4 \to 1$), DFS yığını $1 \to 2 \to 3$ aktifken $3 \to 1$ bir **geri kenardır** (1, 3'ün atası) → çevrim $[1,2,3,1]$, DAG değil; sağda $3 \to 1$ kaldırılmış, geri kenar yok → DAG, topolojik sıra $[4,1,2,3]$. ```{python} #| label: fig-cycle-detect #| fig-cap: "Çevrim tespiti: geri kenar (aktif yığındaki ataya kenar) = çevrim (L10 §10, İMZA figür). SOL panel — çevrimli çizge: 1→2→3→1 üçgeni + 4→1 dış kenarı. DFS özyineleme yolu 1→2→3 amber (aktif yığın). 3'ten 1'e giden kenar KALIN AMBER KESİKLİ + 'geri kenar (back edge)' etiketi — 1, 3'ün ATASIDIR (özyineleme yığınında hâlâ aktif). Sonuç: ÇEVRİM VAR → DAG DEĞİL; çevrim [1,2,3,1], topolojik sıra YOK. SAĞ panel — aynı yapı ama 3→1 kenarı KALDIRILMIŞ (3 çıkışsız): DFS temiz biter, geri kenar yok, çevrim yok → DAG; ters bitiş sırası = topolojik sıra [4,1,2,3]. Full DFS çevrim varsa bir v düğümünden atasına giden kenarı gezer. Veri MOTORDAN: find_cycle({1:[2],2:[3],3:[1],4:[1]})=[1,2,3,1]; find_cycle(3→1 kaldırılmış)=None; topological_order=[4,1,2,3]; verify=True (Solomon 48:20)." #| fig-width: 11.0 #| fig-height: 6.0 # fig-cycle-detect (L10 §10 İMZA): geri kenar = çevrim (çevrimli vs DAG). # Veri MOTORDAN (find_cycle / topological_order / verify_topological). networkx YOK. _CD_POS = {1: (1.10, 1.85), 2: (1.95, 0.55), 3: (0.25, 0.55), 4: (-0.55, 1.85)} _CD_R = 0.26 _CD_DFS_PATH = [1, 2, 3] _CD_PATH_SET = set(_CD_DFS_PATH) def _cd_endpoints(u, v, r=_CD_R): x0, y0 = _CD_POS[u] x1, y1 = _CD_POS[v] dx, dy = x1 - x0, y1 - y0 dist = math.hypot(dx, dy) ux, uy = dx / dist, dy / dist return (x0 + ux * r, y0 + uy * r), (x1 - ux * r, y1 - uy * r) def _cd_node(ax, v, on_path, source=False): x, y = _CD_POS[v] if on_path: fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.6 else: fc, ec, tcol, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.8 if source: lw = 3.2 ax.add_patch(Circle((x, y), _CD_R, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=6)) ax.text(x, y, str(v), ha="center", va="center", fontsize=14, color=tcol, weight="bold", zorder=7) def _cd_dir_edge(ax, u, v, color, lw, dashed=False, zorder=3, mut=16): (x0, y0), (x1, y1) = _cd_endpoints(u, v) ls = (0, (5, 4)) if dashed else "solid" ax.add_patch(FancyArrowPatch( (x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=mut, color=color, linewidth=lw, linestyle=ls, zorder=zorder, shrinkA=0, shrinkB=0)) def _cd_panel(ax, edges, back_edge, title, is_cyclic, cycle_seq, topo=None): for (u, v) in edges: on_path = (u in _CD_PATH_SET and v in _CD_PATH_SET and abs(_CD_DFS_PATH.index(u) - _CD_DFS_PATH.index(v)) == 1 and _CD_DFS_PATH.index(u) < _CD_DFS_PATH.index(v)) \ if (u in _CD_PATH_SET and v in _CD_PATH_SET) else False if on_path: _cd_dir_edge(ax, u, v, COL_ACCENT, 3.0, zorder=4) else: _cd_dir_edge(ax, u, v, COL_SLATE_400, 1.8, zorder=3) if back_edge is not None: bu, bv = back_edge _cd_dir_edge(ax, bu, bv, COL_AMBER_700, 3.4, dashed=True, zorder=5, mut=20) x0, y0 = _CD_POS[bu] x1, y1 = _CD_POS[bv] mx, my = (x0 + x1) / 2.0, (y0 + y1) / 2.0 ax.text(mx - 0.20, my + 0.12, "geri kenar\n(back edge)", ha="right", va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=8) ax.text(mx - 0.20, my - 0.34, f"{bv} = {bu}'ün atası\n(yığında aktif)", ha="right", va="center", fontsize=7.6, color=COL_AMBER_700, style="italic", zorder=8) for v in _CD_POS: _cd_node(ax, v, on_path=(v in _CD_PATH_SET), source=(v == 1)) ax.text(_CD_POS[1][0] + _CD_R + 0.10, _CD_POS[1][1] + _CD_R + 0.16, "DFS yığını: 1→2→3", ha="left", va="bottom", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=8) if is_cyclic: seq_txt = "→".join(str(x) for x in cycle_seq) rfc, rec, rtxt = COL_AMBER_100, COL_AMBER_700, COL_AMBER_700 msg1 = "ÇEVRİM VAR → DAG DEĞİL" msg2 = f"çevrim: {seq_txt} · topolojik sıra YOK" else: rfc, rec, rtxt = "#cfe8da", "#3f7d5e", "#2f6048" msg1 = "ÇEVRİM YOK → DAG" topo_txt = "→".join(str(x) for x in topo) msg2 = f"topolojik sıra (ters bitiş): {topo_txt}" ax.add_patch(FancyBboxPatch( (-1.05, -1.18), 3.30, 0.78, boxstyle="round,pad=0.04,rounding_size=0.10", fc=rfc, ec=rec, linewidth=2.2, zorder=4)) ax.text(0.60, -0.62, msg1, ha="center", va="center", fontsize=9.5, color=rtxt, weight="bold", zorder=6) ax.text(0.60, -0.97, msg2, ha="center", va="center", fontsize=8.6, color=COL_TEXT, family="monospace", zorder=6) ax.text(0.60, 2.62, title, ha="center", va="center", fontsize=11, color=COL_TEXT, weight="bold", zorder=6) ax.set_xlim(-1.20, 2.95) ax.set_ylim(-1.35, 2.85) ax.set_aspect("equal") ax.axis("off") # ---- motor verisi + ASSERT (figür yalnız bunu çizer) ---- _cd_cyc_g = {1: [2], 2: [3], 3: [1], 4: [1]} _cd_ac_g = {1: [2], 2: [3], 3: [], 4: [1]} # 3→1 kaldırılmış _cd_cyc = find_cycle(_cd_cyc_g) assert _cd_cyc == [1, 2, 3, 1], _cd_cyc assert find_cycle(_cd_ac_g) is None _cd_topo = topological_order(_cd_ac_g) assert _cd_topo == [4, 1, 2, 3], _cd_topo assert verify_topological(_cd_ac_g, _cd_topo) is True assert _cd_cyc[0] == _cd_cyc[-1] for _i in range(len(_cd_cyc) - 1): assert _cd_cyc[_i + 1] in _cd_cyc_g[_cd_cyc[_i]] fig, (ax_l, ax_r) = plt.subplots(1, 2, figsize=(11.0, 6.0)) fig.patch.set_facecolor(COL_WHITE) _cd_panel(ax_l, edges=[(1, 2), (2, 3), (4, 1)], back_edge=(3, 1), title="Geri kenar VAR — çevrim", is_cyclic=True, cycle_seq=_cd_cyc) _cd_panel(ax_r, edges=[(1, 2), (2, 3), (4, 1)], back_edge=None, title="Geri kenar YOK — DAG", is_cyclic=False, cycle_seq=None, topo=_cd_topo) fig.suptitle( "Çevrim tespiti: geri kenar (aktif yığındaki ataya kenar) = çevrim", color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975) fig.text(0.5, 0.045, "geri kenar VAR → çevrim (DAG değil, topolojik sıra yok) | " "geri kenar YOK → DAG (ters bitiş sırası = topolojik sıra)", ha="center", va="center", fontsize=9, color=COL_PRIMARY, weight="bold") fig.text(0.5, 0.012, "full DFS çevrim varsa bir v düğümünden atasına giden kenarı gezer " "(Solomon 48:20)", ha="center", va="center", fontsize=8.3, color=COL_SLATE_500, style="italic") fig.subplots_adjust(left=0.02, right=0.98, top=0.90, bottom=0.13, wspace=0.10) plt.show() ``` ## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d15} 1. **DFS** = özyinelemeli "derine in, geri çekil"; BFS eşmerkezli dairelerken DFS dışa fırlar. 2. **Erişilebilirlik**: ebeveyn ağacı $P(v)$ ile *bir* yol (en kısa değil) ver; ağaç (çevrimsiz). 3. **DFS doğruluğu**: uzaklık $k$ üzerinden tümevarım; $u$ ($k$) doğruysa $v$ ($k+1$) de doğru. 4. **Çalışma süresi**: DFS $O(E)$ (yalnız erişilebilir kenarlar); BFS $O(V + E)$ (başta $O(V)$ yer). 5. **Bağlı bileşenler**: full DFS, tüm düğümler üzerinde döngü → $O(V + E)$. 6. **DAG + topolojik sıralama**: $f(u) < f(v)$; benzersiz değil; **ters bitiş sırası** = topolojik sıra. 7. **Çevrim tespiti**: topolojik sıra $\iff$ DAG; geri kenar ($v \to$ atası) çevrimi verir. @fig-dfs-applications dersi tek bir sentez figüründe toplar: ortada **DFS** ($O(V+E)$ özyinelemeli iskelet), dört köşede dört güç — erişilebilirlik, bağlı bileşenler, topolojik sıra, çevrim tespiti — her biri motordan gelen bir mini sonuçla. ```{python} #| label: fig-dfs-applications #| fig-cap: "DFS = tek özyinelemeli iskelet → dört güç (L10 sentezi, İMZA figür). ORTADA büyük amber kutu: DFS — derine in, geri çekil (özyinelemeli visit, O(V+E)). Dört köşede uydu kutusu, merkezden oklarla bağlı, her biri motordan mini sonuç: (1) ERİŞİLEBİLİRLİK O(E) — ebeveyn ağacı (kaynak 1) {1:·, 2:1, 3:2, 4:3, 5:2}, yol 1→2→3→4 en KISA DEĞİL (DFS yolu ≠ en kısa yol). (2) BAĞLI BİLEŞENLER O(V+E) — full DFS sel-doldurma → {a,b,c} {d,e} {f,g,h}, 3 ada. (3) TOPOLOJİK SIRA — ters bitiş sırası (DAG) A→C→B→D, her u→v'de f(u)<f(v) ✓ (build sistemleri make·npm·pip). (4) ÇEVRİM TESPİTİ — geri kenar (aktif yığına) 1→2→3→1, atasına dönen kenar → çevrim (deadlock·import döngüsü). Bağımlılık çözen her sistem içten içe bunu çalıştırır. Veri MOTORDAN: dfs(build_dfs_example(),1)={1:None,2:1,3:2,4:3,5:2}; connected_components=[[a,b,c],[d,e],[f,g,h]]; topological_order(build_dag_example())=[A,C,B,D]; find_cycle({1:[2],2:[3],3:[1]})=[1,2,3,1]." #| fig-width: 11.0 #| fig-height: 7.0 # fig-dfs-applications (L10 §3-10 SENTEZ): tek iskelet → dört güç. # Veri MOTORDAN (dfs / connected_components / topological_order / find_cycle ...). _DA_CC_EDGES = [("a", "b"), ("b", "c"), ("d", "e"), ("f", "g"), ("g", "h")] # ---- motor verisi + ASSERT (figür yalnız bunu yazar) ---- _da_reach = build_dfs_example() _da_parent = dfs(_da_reach, 1) assert _da_parent == {1: None, 2: 1, 3: 2, 4: 3, 5: 2}, _da_parent assert dfs_visit_order(_da_reach, 1)["order"] == [1, 2, 3, 4, 5] _da_cc = make_undirected(_DA_CC_EDGES) _da_comps = connected_components(_da_cc) assert _da_comps == [["a", "b", "c"], ["d", "e"], ["f", "g", "h"]], _da_comps _da_fp, _da_reps = full_dfs(_da_cc) assert len(_da_reps) == 3, _da_reps _da_dag = build_dag_example() _da_topo = topological_order(_da_dag) assert _da_topo == ["A", "C", "B", "D"], _da_topo assert verify_topological(_da_dag, _da_topo) is True assert list(reversed(finishing_order(_da_dag))) == _da_topo _da_cyc = find_cycle({1: [2], 2: [3], 3: [1]}) assert _da_cyc == [1, 2, 3, 1], _da_cyc assert find_cycle(_da_dag) is None fig, ax = plt.subplots(figsize=(11.0, 7.0)) fig.patch.set_facecolor(COL_WHITE) _da_cx, _da_cy = 0.0, 0.0 _da_core_w, _da_core_h = 3.5, 1.7 ax.add_patch(FancyBboxPatch( (_da_cx - _da_core_w / 2, _da_cy - _da_core_h / 2), _da_core_w, _da_core_h, boxstyle="round,pad=0.04,rounding_size=0.18", fc=COL_ACCENT, ec=COL_AMBER_700, linewidth=3.0, zorder=5)) ax.text(_da_cx, _da_cy + 0.36, "DFS", ha="center", va="center", fontsize=21, color=COL_WHITE, weight="bold", zorder=6) ax.text(_da_cx, _da_cy - 0.10, "derine in, geri çekil", ha="center", va="center", fontsize=11.5, color=COL_WHITE, weight="bold", zorder=6) ax.text(_da_cx, _da_cy - 0.45, "(özyinelemeli visit · O(V+E))", ha="center", va="center", fontsize=9, color=COL_AMBER_100, style="italic", zorder=6) _da_sat_w, _da_sat_h = 4.30, 1.86 def _da_satellite(scx, scy, head, head_col, lines): ax.add_patch(FancyBboxPatch( (scx - _da_sat_w / 2, scy - _da_sat_h / 2), _da_sat_w, _da_sat_h, boxstyle="round,pad=0.04,rounding_size=0.14", fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=4)) ax.add_patch(FancyBboxPatch( (scx - _da_sat_w / 2 + 0.06, scy + _da_sat_h / 2 - 0.52), _da_sat_w - 0.12, 0.46, boxstyle="round,pad=0.02,rounding_size=0.08", fc=COL_AMBER_100, ec=head_col, linewidth=1.6, zorder=5)) ax.text(scx, scy + _da_sat_h / 2 - 0.29, head, ha="center", va="center", fontsize=10.5, color=head_col, weight="bold", zorder=6) ly = scy + _da_sat_h / 2 - 0.78 for text, col, bold in lines: ax.text(scx - _da_sat_w / 2 + 0.22, ly, text, ha="left", va="center", fontsize=8.8, color=col, weight="bold" if bold else "normal", family="monospace" if bold else None, zorder=6) ly -= 0.345 ax.add_patch(FancyArrowPatch( (_da_cx, _da_cy), (scx, scy), arrowstyle="-|>", mutation_scale=18, color=COL_AMBER_700, linewidth=2.2, zorder=3, shrinkA=46, shrinkB=58)) _da_dx, _da_dy = 5.05, 2.55 _da_par_str = ", ".join(f"{v}:{('·' if p is None else p)}" for v, p in _da_parent.items()) _da_satellite(-_da_dx, _da_dy, "1 · ERİŞİLEBİLİRLİK O(E)", COL_AMBER_700, [("ebeveyn ağacı (kaynak 1):", COL_TEXT, False), (_da_par_str, COL_AMBER_700, True), ("yol 1→2→3→4 — en KISA DEĞİL", COL_PRIMARY, False), ("(DFS yolu ≠ en kısa yol)", COL_SLATE_500, False)]) _da_comp_str = " ".join("{" + ",".join(c) + "}" for c in _da_comps) _da_satellite(_da_dx, _da_dy, "2 · BAĞLI BİLEŞENLER O(V+E)", COL_AMBER_700, [("full DFS → sel-doldurma:", COL_TEXT, False), (_da_comp_str, COL_AMBER_700, True), (f"{len(_da_comps)} ada (ayrık bileşen)", COL_PRIMARY, False), ("her düğümde dış döngü → tümü", COL_SLATE_500, False)]) _da_topo_str = " → ".join(_da_topo) _da_satellite(-_da_dx, -_da_dy, "3 · TOPOLOJİK SIRA", COL_AMBER_700, [("ters bitiş sırası (DAG):", COL_TEXT, False), (_da_topo_str, COL_AMBER_700, True), ("her u→v kenarında f(u)<f(v) ✓", COL_PRIMARY, False), ("build sistemleri: make · npm · pip", COL_SLATE_500, False)]) _da_cyc_str = " → ".join(str(v) for v in _da_cyc) _da_satellite(_da_dx, -_da_dy, "4 · ÇEVRİM TESPİTİ", COL_AMBER_700, [("geri kenar (aktif yığına):", COL_TEXT, False), (_da_cyc_str, COL_AMBER_700, True), ("atasına dönen kenar → çevrim", COL_PRIMARY, False), ("deadlock · import döngüsü", COL_SLATE_500, False)]) fig.suptitle( "DFS = tek özyinelemeli iskelet → dört güç (Solomon L10 sentezi)", color=COL_TEXT, fontsize=14, weight="bold", y=0.975) ax.text(0.0, -_da_dy - _da_sat_h / 2 - 0.46, "tek özyinelemeli iskeletten dört güç — bağımlılık çözen her sistem " "(make · npm · pip · derleyici) içten içe bunu çalıştırır", ha="center", va="center", fontsize=9, color=COL_SLATE_500, style="italic", zorder=6) ax.set_xlim(-_da_dx - _da_sat_w / 2 - 0.4, _da_dx + _da_sat_w / 2 + 0.4) ax.set_ylim(-_da_dy - _da_sat_h / 2 - 1.0, _da_dy + _da_sat_h / 2 + 0.5) ax.set_aspect("equal") ax.axis("off") plt.tight_layout() plt.show() ``` ::: {.callout-important title="Tek Bir Cümle"} DFS, çizgeyi özyinelemeli olarak derinlemesine gezen tek bir iskelettir; ondan erişilebilirlik ($O(E)$), bağlı bileşenler ve topolojik sıralama/çevrim tespiti — hepsi $O(V + E)$ içinde — doğal olarak türer. ::: ## Kontrol Soruları {#sec-kontrol-sorulari-d15} ::: {.callout-note collapse="true" title="Soru 1: DFS ile BFS arasındaki temel davranış farkı nedir, ve neden DFS O(E) iken BFS O(V+E)?"} **Cevap:** BFS, kaynaktan dışa **katman katman** (seviye kümeleri) ilerler — bir seviye bitmeden sonrakine geçmez. DFS, bir dalda **olabildiğince derine** iner, tıkanınca geri çekilir. Süre farkı uygulamadan gelir: bu dersteki BFS başta $O(V)$ yer ayırdığı için (erişilemeyenler dahil) $O(V + E)$'dir; DFS yalnızca kaynaktan **erişilebilen** kenarlara dokunur, hiç erişilemeyen düğümü görmez, dolayısıyla $O(E)$. (full DFS ise tüm düğümler üzerinde döngü kurduğundan yine $O(V + E)$.) ::: ::: {.callout-note collapse="true" title="Soru 2: DFS'in ürettiği ebeveyn ağacı neden en kısa yolu vermez? Bir örnek ver."} **Cevap:** DFS, bir komşuya "ilk denk geldiği" sırada iner — bu sıra en kısa yolu izlemez. Çevrim çizgesi (halka) uç örnektir: kaynaktan komşu komşuyu özyinelemeli çağırınca son düğüme uzun bir zincirin arkasından varılır, oysa tek kenarla doğrudan gidilebilirdi. DFS o kısa kenarı seçmez. Bu yüzden ağırlıksız en kısa yol için **BFS** kullanılır; DFS yapısal sorular (DAG mı, bileşenler, sıra) içindir. ::: ::: {.callout-note collapse="true" title="Soru 3: “Ters bitiş sırası = topolojik sıralama” iddiasında, v'nin u'dan önce ziyaret edildiği durum neden çevrimsizliğe dayanır?"} **Cevap:** $u \to v$ kenarı var. $v$ önce ziyaret edildiyse, visit($v$) tamamlanmadan $u$'yu görür mü? Görmesi için $v$'den $u$'ya bir yol gerekir — ama $u \to v$ zaten var, $v \to \ldots \to u$ olsaydı bir **çevrim** oluşurdu. Çizge DAG (çevrimsiz) olduğundan bu imkânsız. O hâlde visit($v$), $u$'yu hiç görmeden tamamlanır; ters bitiş sırasında $u$, $v$'den önce gelir (Durum 1 ile aynı sonuç). Çevrimsizlik olmasaydı iddia çökerdi. ::: ::: {.callout-note collapse="true" title="Soru 4: Bir çizgenin DAG olup olmadığını ve (varsa) bir çevrimini nasıl bulursun?"} **Cevap:** full DFS ile ters bitiş sırasını hesapla; her kenar $f(u) < f(v)$ ilişkisine uyuyorsa çizge bir **DAG**'dır (topolojik sıralama var $\iff$ DAG). Bir kenar bu ilişkiyi bozuyorsa çizge DAG değildir → çevrim vardır. Çevrimi *bulmak* için DFS sırasında bir düğümden **atasına** giden bir kenar (geri kenar, back edge) ara; o geri kenar bulunduğu an, atadan o düğüme inen özyineleme zinciri + geri kenar bir çevrim oluşturur. ::: ## Egzersizler {#sec-egzersizler-d15} **Egzersiz 1.** Verilen yönlü bir çizgede, belirli bir kaynaktan DFS gezinme sırasını ve ebeveyn ağacı $P$'yi elle çıkar; aynı çizgede BFS sırasıyla karşılaştır. **Egzersiz 2.** Python'da özyinelemeli DFS'i (yukarıdaki `dfs`) yığın (stack) tabanlı **özyinelemesiz** bir sürüme dönüştür; çıktının ebeveyn ağacının aynı kaldığını doğrula. **Egzersiz 3.** full DFS ile bir yönsüz çizgenin bağlı bileşen sayısını hesaplayan bir fonksiyon yaz; süresinin $O(V + E)$ olduğunu argümanla göster. **Egzersiz 4.** Küçük bir DAG için tüm geçerli topolojik sıralamaları elle listele; ters bitiş sırasının bunlardan biri olduğunu doğrula. **Egzersiz 5.** DFS'i, bir geri kenar (atası ziyarette olan bir komşu) bulduğunda çevrimi düğüm listesi olarak döndürecek şekilde genişlet. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d15} ::: {.callout-warning title="Sonraki: Ders 16 (L11) — Ağırlıklı En Kısa Yollar"} **Ders 16 (L11): Ağırlıklı En Kısa Yollar** — Jason Ku ile, kenarlara **ağırlık** ekliyoruz: artık "en az kenar" değil, "en az toplam ağırlık" arıyoruz. BFS/DFS yetmez; ağırlıklar (hatta negatif ağırlıklar) yeni problemler doğurur. Bu, Bellman-Ford ve Dijkstra'ya giden kapının açılışıdır. **Ders 16 Öncesi Yapılacak:** - Bu dersin egzersizlerini, özellikle Egzersiz 3 (bağlı bileşenler) ve 4 (topolojik sıralama) çöz. - DFS doğruluk kanıtını (uzaklık $k$ tümevarımı) ezberden anlat. - Ana cümleyi tekrar oku: *"DFS tek iskelet; erişilebilirlik, bileşenler, topolojik sıra ondan türer."* ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d15} | Kavram | Tanım | Sayfada | |---|---|---| | **DFS** | Özyinelemeli "derine in, geri çekil"; ebeveyn ağacı $P(v)$ | Böl. 1, 3 | | **Erişilebilirlik** | $s$'den ulaşılan düğümler; $P$ ile bir yol (en kısa değil) | Böl. 2 | | **DFS süresi** | $O(E)$ (yalnız erişilebilir kenarlar); full DFS $O(V + E)$ | Böl. 5, 7 | | **Bağlı bileşen** | Yönsüz çizgede birbirinden erişilebilir küme; full DFS | Böl. 7 | | **DAG** | Yönlü + çevrimsiz çizge | Böl. 8 | | **Topolojik sıra** | $u \to v \Rightarrow f(u) < f(v)$; benzersiz değil | Böl. 8 | | **Bitiş sırası** | visit tamamlanınca ekle; tersi = topolojik sıra | Böl. 9 | | **Çevrim tespiti** | geri kenar ($v \to$ atası); topolojik sıra $\iff$ DAG | Böl. 10 | ## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d15} ::: {.callout-tip title="6 köprü"} Bu ders, "tek özyinelemeli iskelet (DFS), dört güç" sezgisini kurar — köprülerin özeti: 1. **Topolojik sıralama** → build sistemleri (`make`, Bazel), paket bağımlılığı (npm/pip), görev zamanlama: DAG'da çalıştırma sırası. 2. **Çevrim tespiti** → deadlock, import döngüsü, elektronik tablo formül döngüsü, derleyici bağımlılık grafı. 3. **Bağlı bileşenler** → kümeleme, sosyal ağ grupları, görüntü "flood fill", birlik-bul (union-find) alternatifi. 4. **DFS özyineleme** → ağaç/çizge gezme, geri izleme (backtracking) algoritmaları, ifade ağacı değerlendirme. 5. **Erişilebilirlik** → ulaşılabilir kod analizi (derleyici), çöp toplama (mark-and-sweep), bağımlılık kapanışı. 6. **$O(V + E)$ doğrusal** → seyreklik bilinci: gerçek çizgeler seyrek; bir gezinmede her kenara bir kez dokun. ::: --- ::: {.callout-important title="Tek bir şey alıp gideceksen"} DFS, "derine in, geri çekil" diyen tek bir özyinelemeli iskelettir — ama o tek iskeletten erişilebilirlik ($O(E)$), bağlı bileşenler ($O(V + E)$), topolojik sıralama ve çevrim tespiti çıkar. Bağımlılık çözen her sistem (make, paket yöneticisi, derleyici) içten içe bunu çalıştırır. :::