Parcours de graphes — DFS, BFS, cycles, chemins

Introduction

Un graphe modélise des entités reliées entre elles : pages web et hyperliens, villes et routes, routeurs et liaisons réseau, cases d'un labyrinthe et passages entre elles. Le parcours d'un graphe est l'opération de base : visiter chaque sommet une fois, dans un ordre choisi, pour répondre à une question — « ce sommet est-il atteignable ? », « y a-t-il un cycle ? », « quel est le chemin le plus court ? ».

Cette section suppose la familiarité avec la représentation d'un graphe par matrice d'adjacence ou liste de successeurs — voir le chapitre Structures de données (TA02). Ici, on les explore.

Représentation : liste de successeurs

On utilise la représentation la plus économique pour les graphes peu denses : un dictionnaire qui à chaque sommet associe la liste de ses voisins.

# Graphe orienté à 6 sommets — exemple du cours.
graphe = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D', 'E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

Parcours en profondeur (DFS)

Le parcours en profondeur (Depth-First Search) plonge le plus loin possible le long d'une branche avant de remonter pour explorer une autre. Naturellement récursif, il peut aussi s'écrire de manière itérative avec une pile explicite. C'est exactement la façon dont on explore un labyrinthe en s'enfonçant toujours dans le couloir le plus profond — quand on rencontre un cul-de-sac, on revient en arrière jusqu'au dernier embranchement non exploré.

def dfs(graphe, depart):
    visite = set()
    def explore(s):
        visite.add(s)
        for voisin in graphe[s]:
            if voisin not in visite:
                explore(voisin)
    explore(depart)
    return visite

# Version itérative — utile quand la récursion risque de déborder la pile.
def dfs_iter(graphe, depart):
    visite = set()
    pile = [depart]
    while pile:
        s = pile.pop()                # LIFO
        if s in visite:
            continue
        visite.add(s)
        for voisin in graphe[s]:
            if voisin not in visite:
                pile.append(voisin)
    return visite

Invariant : à chaque appel récursif, l'ensemble visite contient tous les sommets atteints par la branche en cours. Tout sommet inséré sera traité exactement une fois — le coût total est en $\mathcal{O}(|V| + |E|)$ : chaque sommet ouvert une fois, chaque arête parcourue une fois.

Parcours en largeur (BFS)

Le parcours en largeur (Breadth-First Search) visite les sommets par ordre de distance au sommet de départ : tous les voisins immédiats d'abord, puis les voisins de voisins, etc. Il utilise une file (FIFO). On peut le visualiser comme les ondes concentriques d'un caillou jeté dans l'eau — chaque cercle agrandit la zone explorée d'une unité de distance.

from collections import deque

def bfs(graphe, depart):
    visite = {depart}
    file = deque([depart])
    while file:
        s = file.popleft()
        for voisin in graphe[s]:
            if voisin not in visite:
                visite.add(voisin)
                file.append(voisin)
    return visite

Coût identique : $\mathcal{O}(|V| + |E|)$. La différence avec DFS est l'ordre de découverte — BFS garantit la plus courte distance en nombre d'arêtes, DFS ne le garantit pas.

Recherche d'un chemin

Adapter le BFS pour reconstruire un chemin : on mémorise le prédécesseur de chaque sommet à mesure qu'on le découvre, puis on remonte.

def chemin_bfs(graphe, depart, arrivee):
    if depart == arrivee:
        return [depart]
    pred = {depart: None}
    file = deque([depart])
    while file:
        s = file.popleft()
        for voisin in graphe[s]:
            if voisin not in pred:
                pred[voisin] = s
                if voisin == arrivee:        # reconstruction
                    chemin = [arrivee]
                    while pred[chemin[-1]] is not None:
                        chemin.append(pred[chemin[-1]])
                    return list(reversed(chemin))
                file.append(voisin)
    return None                              # arrivée inatteignable

Détection de cycle

Dans un graphe non orienté, on détecte un cycle par DFS : en explorant depuis un sommet s, si l'on rencontre un voisin déjà visité autre que celui d'où l'on vient, c'est un cycle.

def a_un_cycle(graphe):
    visite = set()
    def explore(s, parent):
        visite.add(s)
        for voisin in graphe[s]:
            if voisin not in visite:
                if explore(voisin, s):
                    return True
            elif voisin != parent:           # déjà vu et pas le père : cycle
                return True
        return False
    for s in graphe:
        if s not in visite:
            if explore(s, None):
                return True
    return False

Deux exemples concrets

Labyrinthe : chaque case est un sommet, chaque passage une arête. Un BFS depuis l'entrée trouve la sortie en un minimum de pas ; un DFS explore récursivement les couloirs et fonctionne très bien quand on cherche juste un chemin.

Routage Internet : le réseau est un graphe de routeurs reliés par des liaisons physiques. Le protocole OSPF (vu au chapitre Architectures matérielles, systèmes d'exploitation et réseaux, TC03) construit la table de routage en cherchant les plus courts chemins — il utilise une variante pondérée de BFS appelée algorithme de Dijkstra.

Pour aller plus loin

L'algorithme de Dijkstra étend le BFS aux graphes pondérés (chaque arête a un coût) : il utilise une file de priorité au lieu d'une file ordinaire. Hors programme strict de Terminale, mais incontournable dès qu'on parle de plus court chemin réel — c'est lui qui fait fonctionner OSPF et, en partie, votre GPS.