Graf Dolaşımı
Graf dolaşımı, bir grafın düğümlerini ve kenarlarını sistematik olarak ziyaret etme işlemidir; genişlik öncelikli arama (BFS) seviye seviye keşfederken, derinlik öncelikli arama (DFS) geri izlemeden önce mümkün olduğunca derine iner ve birlikte çoğu grafik algoritmasının temelini oluşturmaktadır.
Tanım
Graf dolaşımı, bir grafın her düğümünü (ve her kenarını) sistematik bir sırayla ziyaret etme sürecidir; genişlik öncelikli arama, düğümleri bir kaynaktan uzaklık sırasına göre ziyaret ederken, derinlik öncelikli arama her yolu geri izlemeden önce sonuna kadar takip etmektedir.
Kapsam
Bu konu, iki temel graf arama stratejisi olan genişlik öncelikli arama (BFS) ve derinlik öncelikli arama (DFS)'yi, bunların kuyruk ve yığın tabanlı uygulamalarını ve ortaya çıkardıkları yapısal bilgileri — erişilebilirlik, bağlı bileşenler, ağırlıksız graflardaki en kısa yollar, topolojik sıralama, döngü tespiti ve güçlü bağlı bileşenler — kapsamaktadır. Dolaşım üzerine inşa edilmekle birlikte ayrı olarak ele alınan ağırlıklı en kısa yollar ve akış problemleri kapsam dışıdır.
Temel sorular
- BFS ve DFS, düğümleri ziyaret etme sıraları açısından nasıl farklılık gösterir ve her biri neyi ortaya koyar?
- BFS, ağırlıksız bir grafikte en kısa yolları nasıl hesaplar?
- DFS, topolojik sıralamayı, döngü tespitini ve bileşen ayrıştırmayı nasıl sağlar?
- Her iki dolaşım da neden düğüm sayısı artı kenar sayısına göre doğrusal zamanda çalışır?
- Ziyaret edilen işaretleyiciler ve sınır yapıları, düğümlerin tekrar ziyaret edilmesini önlemek için nasıl kullanılır?
Anahtar kavramlar
- genişlik öncelikli arama (BFS)
- derinlik öncelikli arama (DFS)
- ziyaret edilen küme
- kuyruk ve yığın sınırları
- bağlı bileşenler
- topolojik sıralama
- döngü tespiti
- güçlü bağlı bileşenler
Temel kuramlar
- Genişlik öncelikli arama ve ağırlıksız en kısa yollar
- BFS, bir kuyruk kullanarak düğümleri kaynaktan uzaklığa göre artmayan sırada ziyaret etmekte, böylece kaynaktan her erişilebilir düğüme olan minimum kenar sayısını doğrusal zamanda hesaplamaktadır.
- Derinlik öncelikli arama ve doğrusal graf algoritmaları
- DFS, keşif ve bitiş zamanları ile kenar sınıflandırması sayesinde, Tarjan tarafından sistemleştirildiği üzere, topolojik sıralama, döngü tespiti ve güçlü bağlı bileşenleri bulma için doğrusal zamanlı algoritmalar sağlamaktadır.
Klinik önem
Dolaşım algoritmaları yaygın olarak kullanılmaktadır: BFS, ağırlıksız ağlarda en kısa atlama sayılarını bulmakta ve web tarayıcıları ile eşler arası yayınların temelini oluşturmaktadır; DFS ise topolojik sıralama aracılığıyla bağımlılık çözümlemesini ve derleme sistemlerini, kilitlenme tespitini, labirent ve bulmaca çözümünü, sosyal ve biyolojik ağlarda bileşen analizini sağlamaktadır.
Tarihçe
Genişlik öncelikli arama, Moore'un 1959'daki labirent yönlendirme çalışmasına ve ilgili bağımsız çabalara dayanmaktadır. Derinlik öncelikli arama, 1972 yılında Robert Tarjan tarafından titiz bir algoritmik temele oturtulmuş olup, güçlü bağlı bileşenler ve iki bağlantılılık için geliştirdiği doğrusal zamanlı algoritmalar, DFS'yi güçlü bir genel araç olarak ortaya koymuştur.
Öne çıkan isimler
- Robert Tarjan
- Edward F. Moore
- John Hopcroft
İlgili konular
Temel eserler
- tarjan1972
- cormen2009
Sıkça sorulan sorular
- DFS yerine BFS'yi ne zaman kullanmalıyım?
- Kenar sayısı açısından en kısa yolu bulmanız gerektiğinde veya grafı bir kaynaktan uzaklık sırasına göre keşfetmek istediğinizde BFS kullanılması önerilmektedir. Yapısal problemler — topolojik sıralama, döngü tespiti, bağlı veya güçlü bağlı bileşenler — için ise DFS tercih edilmektedir; bu tür durumlarda derinlemesine keşfetme ve geri izleme doğal bir yaklaşımdır.
- BFS ve DFS neden her ikisi de doğrusal zamanda çalışır?
- Her düğüm bir kez ziyaret edildi olarak işaretlenmekte ve işlenmektedir; her kenar ise sabit sayıda incelenmektedir. Bu nedenle, toplam iş miktarı düğüm sayısı artı kenar sayısıyla orantılı olup, O(V + E) olarak ifade edilmektedir.