Dərinlik üzrə axtarış (DFS)

Dərinlik üzrə axtarış (DFS) qrafı labirint kimi gəzir: bir yolla mümkün qədər dərinə gedir, çıxılmaz yerdə geri qayıdıb növbətini yoxlayır. Ona iki şey lazımdır: ziyarət edilmiş təpələr çoxluğu (yoxsa dövrləri olan qrafda sonsuz dövr edər) və hara qayıtmağı yadda saxlayan stek. Qraflar Qrafların təsviri mövzusundakı kimi saxlanır; nümunələrdə qonşuluq siyahılarından ibarət lüğət işlədilir.

Rekursiv DFS

visit(u) təpəni işarələyir, sonra hələ ziyarət edilməmiş hər qonşu üçün özünü çağırır. Qonşuların sırası ziyarət sırasını təyin edir.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def dfs(graph, start):
    visited = set()
    order = []

    def visit(u):
        visited.add(u)                    # mark on entry
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visit(v)

    visit(start)
    return order

print(dfs(graph, "A"))

['A', 'B', 'D', 'E', 'F', 'C']

Burada D çıxılmazdır: DFS B-yə qayıdıb E ilə davam edir. A-C tili işlədilmir: DFS F-dən C-yə çatanda A artıq ziyarət edilib (geri til). Qalın tillər DFS ağacını təşkil edir.

Stek ilə iterativ DFS

Rekursiya stekini öz stekimizlə əvəz etmək olar: pop ən son əlavə olunan təpəni götürür (LIFO). Qonşuları reversed ilə əlavə etsək, ziyarət sırası rekursiyadakı ilə eyni olur.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}