Le parcours en profondeur (DFS)

Plonger le plus loin possible

Le parcours en profondeur (en anglais (Depth-First Search), DFS) adopte la stratégie inverse du BFS : au lieu d'explorer en largeur, il s'enfonce dans une branche jusqu'au bout, puis revient en arrière (« backtrack ») pour explorer les branches non visitées. C'est la stratégie qu'on emploie instinctivement pour sortir d'un labyrinthe : suivre un couloir jusqu'au mur, puis rebrousser chemin.

Depart en A, DFS :

        (A)                ordre possible :  A  B  D  E  C
        /  \                (on plonge A->B->D, mur,
      (B)   (C)              on remonte, B->E, mur,
      /  \                   on remonte jusqu'à A, puis C)
    (D)   (E)

Version récursive : la plus naturelle

Le DFS s'écrit très élégamment avec la récursivité, qui utilise implicitement la pile d'appels.

def dfs(graphe, s, visites=None):
    if visites is None:
        visites = set()
    visites.add(s)                 # (marquer comme visite)
    print(s, end=" ")
    for voisin in graphe[s]:
        if voisin not in visites:
            dfs(graphe, voisin, visites)   # (on plonge !)

L'appel récursif « plonge » dans le voisin avant de traiter les suivants : c'est exactement ce qui produit la descente en profondeur.

Version itérative : avec une pile

On peut aussi l'écrire sans récursivité, en remplaçant la file du BFS par une pile (LIFO). C'est le seul changement de fond entre les deux parcours.

def dfs_iteratif(graphe, depart):
    visites = set()
    pile = [depart]
    while pile:
        s = pile.pop()             # (on sort le PLUS RECENT : LIFO)
        if s not in visites:
            visites.add(s)
            print(s, end=" ")
            for voisin in graphe[s]:
                pile.append(voisin)

BFS ou DFS : le même squelette, une structure de données

C'est le point le plus important du chapitre. BFS et DFS sont le même algorithme : partir d'un sommet, retirer un élément d'une réserve, le traiter, y ajouter ses voisins non visités. Seule la nature de la réserve change l'ordre d'exploration :

Parcours	Réserve	Comportement	Trouve le + court chemin ?
BFS	file (FIFO)	par vagues, en largeur	oui (non pondéré)
DFS	pile (LIFO)	plonge en profondeur	non

À quoi sert le DFS ?

Le DFS excelle pour des problèmes où il faut explorer toutes les possibilités : détecter un cycle, trouver les composantes connexes (les « îlots » d'un graphe), résoudre un labyrinthe, ou faire un tri topologique (ordonner des tâches selon leurs dépendances).

En résumé

Le DFS plonge au fond d'une branche avant de rebrousser chemin, à l'aide de la pile (explicite, ou implicite via la récursivité). Il partage exactement la même structure que le BFS : remplacer la file par une pile suffit à passer de l'un à l'autre. Le DFS ne garantit pas le plus court chemin, mais il est idéal pour explorer exhaustivement un graphe.