#Parcours de graphes : BFS et DFSCopier le lien

Prérequis : structures liste, ensemble, pile et file du parcours L2 ; notion de complexité linéaire.

Objectifs d'apprentissage : implémenter BFS et DFS (itératif et récursif) ; démontrer que BFS calcule les plus courts chemins en nombre d'arêtes ; utiliser le DFS pour tri topologique et détection de cycle ; choisir le parcours adapté au problème.

#1. Parcours en largeur (BFS)Copier le lien

Le parcours en largeur explore d'abord tous les nœuds à distance 1 du départ, puis ceux à distance 2, et ainsi de suite. Il utilise une file (FIFO) : les nœuds entrent dans l'ordre de leur découverte, donc par couches de distance croissante.

Principe :

1. Enfiler le nœud de départ et le marquer découvert.
2. Tant que la file n'est pas vide : défiler un nœud, puis pour chaque voisin non découvert, le marquer et l'enfiler.

Remarquez le marquage à l'enfilement (et non au dépilement) : sans lui, un même nœud pouvait entrer plusieurs fois dans la file, ce qui gonflerait la mémoire sans bénéfice.

1from collections import deque2 3def bfs(graphe, depart):4    """Parcours en largeur ; renvoie l'ordre de visite.5    graphe : dict sommet -> liste de voisins."""6    decouvert = {depart}7    file = deque([depart])8    ordre = []9    while file:10        u = file.popleft()11        ordre.append(u)12        for v in graphe.get(u, []):13            if v not in decouvert:14                decouvert.add(v)

Propriété centrale : BFS depuis s calcule le minimum d'arêtes de s à chaque sommet atteignable. Preuve (induction sur les couches) : les sommets à distance d+1 sont exactement les voisins non visités des sommets à distance d, découverts au tour d après. C'est le plus court chemin des graphes non pondérés ; dès que les arêtes ont des poids, c'est Dijkstra qu'il faut.

#Animation interactiveCopier le lien

Entrées : un graphe non pondéré et un sommet source, au choix dans le composant. Sorties : l'ordre de visite et, en mode BFS, la couche (distance) de chaque sommet. Test de lecture : pariez l'ordre de visite complet avant de lancer, puis expliquez chaque divergence ; elles viennent presque toujours de l'ordre d'énumération des voisins.

#2. Parcours en profondeur (DFS)Copier le lien

Le parcours en profondeur pousse aussi loin que possible le long d'une branche avant de revenir. Deux écritures équivalentes :

1def dfs_iteratif(graphe, depart):2    """DFS avec pile explicite ; évite la limite de récursion."""3    decouvert = set()4    pile = [depart]5    ordre = []6    while pile:7        u = pile.pop()8        if u in decouvert:9            continue10        decouvert.add(u)11        ordre.append(u)12        # inverser pour retrouver l'ordre de la version récursive13        for v in reversed(graphe.get(u, [])):14            if v not in decouvert:

Le test au dépilement (et non à l'empilement) est correct ici, mais un sommet peut alors entrer plusieurs fois dans la pile ; la garde if u in decouvert: continue filtre les doublons. La version récursive est plus courte à écrire mais limitée par la profondeur de pile de Python (environ 1000 par défaut) : sur un long chemin, préférez la pile explicite.

#Animation : différences clés BFS vs DFSCopier le lien

#3. ComparaisonCopier le lien

#4. ApplicationsCopier le lien

BFS : plus court chemin en nombre d'arêtes (labyrinthe, réseau social), niveaux d'un arbre, propagation d'une information couche par couche, puzzles à coups unitaires (taquin).

DFS : tri topologique d'un graphe de dépendances (ordre d'assemblage, ordre d'évaluation), détection de cycles (ci-dessous), composantes fortement connexes (Kosaraju, Tarjan), exploration de labyrinthe avec retour arrière (parcours exhaustif).

#5. Détection de cycle par DFSCopier le lien

Dans un graphe orienté, un cycle existe si le DFS rencontre un nœud « en cours » d'exploration. Trois états suffisent : non visité (0), en cours (1), terminé (2). Rencontrer un nœud en cours remonte une arête de retour ; rencontrer un nœud terminé est inoffensif (chemin déjà clos).

1def contient_cycle(graphe):2    """Détection de cycle dans un graphe orienté.3    0 = non visité, 1 = en cours, 2 = terminé."""4    etat = {u: 0 for u in graphe}5 6    def dfs(u):7        etat[u] = 18        for v in graphe.get(u, []):9            if etat[v] == 1:      # arête de retour : cycle10                return True11            if etat[v] == 0 and dfs(v):12                return True13        etat[u] = 214        return False

Dans un graphe non orienté, la même idée marche en excluant le parent direct de l'arête empruntée (sinon aller-retour entre deux voisins compte comme un cycle).

#Playground : distances et reconstruction de cheminCopier le lien

Entrées du playground : le dictionnaire d'adjacence et les deux sommets. Sorties : la distance en arêtes et la liste du chemin. Modifiez une arête et observez que seule la couche concernée change, jamais l'algorithme.

#6. ComplexitéCopier le lien

Chaque sommet est découvert une fois, chaque arête examinée une fois (deux fois en non orienté) ; l'espace couvre les structures de découverte et la file ou la pile, bornées par V.

#7. Exercices avec vérificationCopier le lien

1. Tri topologique : à partir du DFS, Produisez un ordre compatible avec les dépendances du graphe sans_cycle ci-dessus. Vérification : pour l'ordre obtenu, chaque arête u -> v place u avant v ; une réponse valide pour l'exemple est [A, C, B, D] (plusieurs solutions existent).
2. Composantes connexes : comptez les composantes d'un graphe non orienté en relançant DFS depuis chaque sommet non visité. Vérification : sur le graphe d'exemple plus un sommet isolé 'Z', la réponse est 2.
3. BFS bidirectionnel (pour aller plus loin) : explorez depuis départ et arrivée en alternant, et arrêtez quand les deux frontières se touchent. Vérification : sur le graphe d'exemple entre A et F, la rencontre se produit à la couche 1 de chaque côté.

#Mini-quizCopier le lien