Parcours en profondeur (DFS)

Le DFS (Depth-First Search), c'est l'oppose du BFS. Au lieu d'explorer niveau par niveau, tu explores le plus loin possible dans une direction avant de revenir en arriere. C'est comme explorer un labyrinthe : tu avances dans un couloir jusqu'au bout, puis tu fais demi-tour pour essayer un autre chemin.

La difference avec le BFS tient a une seule chose : au lieu d'une file (FIFO), on utilise une pile (LIFO, dernier entre premier sorti). En Python, une simple liste avec pop() fait l'affaire.

Attention : avec la pile, il faut vérifier si le noeud a deja ete visite au moment ou tu le depiles, pas quand tu l'empiles (car un noeud peut etre empile plusieurs fois).

graphe = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']}
dfs(graphe, 'A') visite tous les noeuds

Écris une fonction dfs(graphe, depart) en version iterative (avec une pile).

Tests (2/4)

DFS visite tout

g = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']}
résultat = dfs(g, 'A')
assert set(résultat) == {'A', 'B', 'C', 'D'}

Depart inclus

g = {'A': ['B'], 'B': ['A']}
résultat = dfs(g, 'A')
assert résultat[0] == 'A'

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

def dfs(graphe, depart):
    visites = []
    vus = set()
    pile = [depart]
    while pile:
        noeud = pile.pop()
        if noeud not in vus:
            vus.add(noeud)
            visites.append(noeud)
            for voisin in graphe.get(noeud, []):
                if voisin not in vus:
                    pile.append(voisin)
    return visites

← Parcours en largeur (BFS) Trouver un chemin dans un … →

solution.py

Bravo!

Parcours en profondeur (DFS)

Tests (2/4)

Indices (3 disponibles)

Solution officielle