Derinlemesine Arama (DFS)

Graflar O(V + E) O(V)

Geri izlemeden önce her dalda olabildiğince derine dalar — özyineleme veya yığınla gerçeklenir.

sıra0

Başlangıç düğümü

1/44

dfs(0) çağrıldı — 0 ziyaret edildi olarak işaretlendi.

DeğişmezYığındaki her düğüm mevcut düğümün atasıdır; kaynaktan gelen yol tam olarak o yığındır.

mevcutsınırziyaret edildiağaç kenarı

dfs.c

#define V 6
 
void dfs(int graph[V][V], int u, int visited[V]) {
    visited[u] = 1;
    printf("%d ", u);
    for (int v = 0; v < V; v++) {
        if (graph[u][v] && !visited[v])
            dfs(graph, v, visited);
    }
}

Derinlemesine Arama (DFS) nasıl çalışır?

Bir dalı gidebildiği kadar derine izle, sonra son çatala geri dön. Dönüş yolunu özyineleme yığını kendisi hatırlar.

Ne zaman kullanılır?

Döngü tespiti, topolojik sıralama, bağlı bileşenler, labirent/geri izleme problemleri.