DFS DFS
Önce derinlik araması ( DFS), grafiklerdeki ana algoritmalardan biridir. Algoritma O(N + M) şeklinde çalışır.
Algoritma
Başlangıç olarak tepeden başlıyoruz, bu tepenin çocuklarını ele alıyoruz ve onları hiç girmemişsek onlardan DFS başlatıyoruz.
|
DFS DFS
Önce derinlik araması ( DFS), grafiklerdeki ana algoritmalardan biridir. Algoritma O(N + M) şeklinde çalışır.
Algoritma
Başlangıç olarak tepeden başlıyoruz, bu tepenin çocuklarını ele alıyoruz ve onları hiç girmemişsek onlardan DFS başlatıyoruz.
|
İkili grafik
İki parçalı grafik - köşeleri iki kümeye bölünebilen bir grafik, böylece her bir kenar birbirine bağlanır. farklı kümelerden köşeler.
Genellikle ikili grafikler bağlamında, renkler köşeler kavramı kullanılır. Bir grafiği iki parçaya bölmeye köşelerini iki farklı renkle renklendirme denir. Her kenar, farklı renkteki köşeleri birleştirmelidir.
DFS.
Algoritma
Boyayı isteğe bağlı bir renge boyadığımız isteğe bağlı bir tepe noktasından başlatıyoruz.
Her kenar boyunca geçerken, bir sonraki köşeyi zıt renge boyayın.
Komşu köşeler üzerinde yineleme yaparken, halihazırda geçerli olanla aynı renge boyanmış bir tepe noktası bulursak grafikte tek döngü vardır, bu da bunun iki parçalı olmadığı anlamına gelir.
|
Algoritma şu şekilde açıklanabilir:
n köşesi ve m kenarı olan yönlendirilmiş bir grafik verildi. Köşelerini, her bir kenar daha düşük numaralı bir tepe noktasından daha yüksek numaralı bir tepe noktasına gidecek şekilde yeniden numaralandırmak gerekir.
Başka bir deyişle, grafiğin tüm kenarları tarafından verilen sıraya karşılık gelen bir köşe permütasyonu (topolojik sıra) bulmak gerekir.
Derinlik öncelikli aramayı kullanacağız (dfs(v))
\(dfs(v)\) 'den çıkış anında tepe noktamızı bir listenin başına eklersek, o zaman sonunda bu listede topolojik bir sıralama elde edersiniz.
Böylece istenen topolojik sıralama — bu, çıkış zamanlarının azalan sırasına göre sıralanır.
|