Temeller
Graf teorisi temelleri
Düğüm, kenar, derece, yol ve döngüler; komşuluktan BFS/DFS karmaşıklığı.
Soru: 10⁵ düğümlü, 2·10⁵ kenarlı bir graf için BFS doğru mu?
Komşuluk listesiyle evet: O(V + E) = 3·10⁵. Komşuluk matrisiyle ölürsün: O(V²) = 10¹⁰. Bu sayfa, hangi gösterimin neden hangi maliyeti getirdiğini ve derece toplamının neden V+E’yi verdiğini açar.
Sayılarla: gösterim karşılaştırması
| Gösterim | BFS/DFS | Tek komşu sorgu | Bellek |
|---|---|---|---|
| Komşuluk listesi | O(V + E) | O(degree) | O(V + E) |
| Komşuluk matrisi | O(V²) | O(1) | O(V²) |
Seyrek graf (E ~V): komşuluk listesi çok daha hızlı. Yoğun graf (E ~V²): matris birebir. Mülakatlarda neredeyse her zaman seyrek → komşuluk listesi.
Nereden gelir?
Derece toplamı kuralı
Her kenar iki düğüme değer, bu yüzden Σ degree(v) = 2E. BFS/DFS her düğümü bir kez ve her kenarı bir kez (yönsüz) veya iki kez (yönlü) gezer → toplam V + E.
BFS katman maliyeti
BFS, kuyrukla kat kat ilerler. Her katmanda, o katmanın tüm düğümlerinin komşularını gezersin. Toplam gezilen kenar = E (her kenar bir kez), toplam gezilen düğüm = V. Bellek: kuyruk en kötü O(V). Bu yüzden en kısa yol (yönsüz graf, birimsiz kenar) BFS’dir ve maliyeti O(V + E).
Ağaç = döngüsüz bağlı graf
n düğüm, n-1 kenar, tam olarak bir yol her çift arasında. Ağaçta BFS/DFS hâlâ O(V + E) = O(n) (E = n-1). Tree DFS (LC 100, 104, 110) ve tree pattern’ler bu ailenin özel hâlidir.
Tuzak: “matris her zaman daha hızlı çünkü O(1) komşu sorgu”
Yanlış yön: O(1) tek bir (u,v) çifti için. Ama BFS, bir düğümün tüm komşularını istiyor; matriste V tane hücreyi tara. degree(u) küçükse (seyrek graf) komşuluk listesi çok daha hızlı; çünkü sadece gerçek komşuları gezersin. 10⁵ düğümde matris her BFS’ta 10¹⁰ hücre, oysa liste 2·10⁵ kenar.
Sıradaki adım
- graph-dfs kalıbı - DFS’in kullanıldığı DSA yerleri.
- grid-graph-bfs kalıbı - ızgara üzerinde BFS.
- tree-dfs kalıbı - ağaç, döngüsüz grafdır.
- LC 200 Number of Islands - grid-graph BFS/DFS.
- LC 207 Course Schedule - directed graph + döngü tespiti.
- LC 261 Graph Valid Tree - ağaç = n-1 kenar + bağlı.
Alıştırma
Sağdaki grafa tıklayıp birkaç kenar ekle. Her düğümün derecesini, kenar eklendikçe artmasını izle. Şimdi dereceleri topla: 2 × kenar sayısına eşit mi? Bu, Σ degree = 2E kuralının somut hâlidir.
Kenar ekle: -
Derece