BFS pour les plus courts chemins

1. Le principe du parcours en largeur (BFS)

Imaginez que vous êtes au centre d'un labyrinthe et que vous cherchez la sortie la plus proche. Une stratégie serait d'explorer d'abord toutes les salles directement connectées à votre position. Puis, depuis ces salles, explorer toutes les nouvelles salles adjacentes, et ainsi de suite, en vous éloignant progressivement, couche par couche. C'est précisément l'intuition du BFS.

Le BFS explore un graphe par "vagues" successives à partir d'un sommet source s.

1. Il visite s.
2. Il visite tous les voisins de s.
3. Il visite tous les voisins non encore visités des voisins de s.
4. Et ainsi de suite, jusqu'à ce que tous les sommets accessibles depuis s aient été visités.

Pour gérer cette exploration par "couches", l'algorithme s'appuie sur une structure de données que vous connaissez : la file (queue en anglais), qui suit le principe "Premier entré, premier sorti" (FIFO).

Pour une analogie visuelle très parlante de ce mécanisme, je vous invite à regarder le début de la vidéo suivante.

Cette exploration par niveaux est la raison pour laquelle le BFS est l'algorithme idéal pour trouver le plus court chemin en nombre d'arêtes. Le premier chemin trouvé par le BFS pour atteindre un sommet v depuis un sommet s est nécessairement le plus court, car tout autre chemin passerait par des sommets situés dans des couches plus éloignées ou de même niveau, et serait donc plus long ou de longueur égale.

2. L'algorithme BFS pas à pas

Voyons maintenant comment l'algorithme opère concrètement, en utilisant une file et un moyen de marquer les sommets déjà visités pour éviter les traitements redondants et les boucles infinies.

L'algorithme général est le suivant :

1. Initialiser une file vide et y ajouter le sommet de départ s.
2. Marquer s comme visité. On utilise souvent un tableau visite et on peut aussi stocker la distance de chaque sommet à s dans un tableau distance. On initialise distance[s] = 0.
3. Tant que la file n'est pas vide :
   a. Défiler un sommet u.
   b. Pour chaque voisin v de u :
   i. Si v n'a pas été visité :
   - Marquer v comme visité.
   - Mettre à jour sa distance : distance[v] = distance[u] + 1.
   - Enfiler v.

Pour voir cet algorithme en action, la vidéo ci-dessous détaille une exécution pas à pas.

L'image suivante résume parfaitement une exécution sur un graphe orienté.

3. Du parcours au calcul des plus courts chemins

Le parcours simple nous dit si un sommet est accessible, mais pour l'Agrégation, il est crucial de pouvoir exploiter ce parcours. L'application principale du BFS est le calcul des plus courts chemins en termes de nombre d'arêtes.

Comme vu précédemment, la distance d'un nouveau sommet v découvert depuis u est simplement distance[u] + 1. Cela nous donne la longueur du plus court chemin.

Mais comment reconstruire le chemin lui-même ?

On utilise pour cela un tableau supplémentaire, predecesseur. Lorsque l'on découvre un sommet v depuis u, on mémorise ce fait en stockant predecesseur[v] = u. Une fois le BFS terminé (ou la destination atteinte), il suffit de remonter la chaîne des prédécesseurs depuis le sommet d'arrivée jusqu'au sommet de départ pour reconstituer le chemin.

La vidéo de WilliamFiset explique très bien cette double procédure : une première passe BFS pour calculer les distances et les prédécesseurs, et une seconde passe pour reconstruire le chemin.

4. Formalisation et Implémentation

Pour une préparation au niveau de l'Agrégation, la maîtrise du pseudo-code formel est indispensable. Le document suivant présente l'algorithme de manière rigoureuse.

Analyse de complexité :
Comme indiqué dans le document, la complexité du BFS est un résultat fondamental à connaître :

• Complexité temporelle : $O(|S|+|A|)$ (ou $O(n+m)$ avec $n$ sommets et $m$ arêtes). Chaque sommet est enfilé/défilé une seule fois ($O(|S|)$), et chaque arête est examinée une seule fois (ou deux pour un graphe non orienté), d'où $O(|A|)$.
• Complexité spatiale : $O(|S|)$. Dans le pire cas, la file peut contenir presque tous les sommets. Les tableaux visite, distance et predecesseur occupent également un espace proportionnel au nombre de sommets.

Implémentation en Python :

Étant donné votre aisance en Python, l'implémentation est directe. La structure la plus efficace pour une file est collections.deque. Voici un squelette d'implémentation pour un graphe représenté par une liste d'adjacence.

from collections import deque

def bfs_shortest_path(graph, start, end):



    # graph: dictionnaire {sommet: [voisins]}
    # start, end: sommets de départ et d'arrivée

    if start == end:
        return [start]

    queue = deque([(start, [start])]) # La file stocke (sommet_courant, chemin_jusqu'ici)
    visited = {start}

    while queue:
        current_node, path = queue.popleft()

        for neighbor in graph.get(current_node, []):
            if neighbor not in visited:
                if neighbor == end:
                    return path + [neighbor] # Chemin trouvé
                
                visited.add(neighbor)
                new_path = path + [neighbor]
                queue.append((neighbor, new_path))

    return None # Aucun chemin trouvé

Note : Cette implémentation stocke le chemin entier dans la file, ce qui peut être gourmand en mémoire pour de longs chemins. L'approche avec un tableau de prédécesseurs est généralement plus efficace en espace.

5. Exercice d'application

Un cas d'usage classique du BFS est la résolution de problèmes sur des grilles (labyrinthes, jeux, etc.), où la grille peut être vue comme un graphe implicite : chaque case est un sommet, et les arêtes relient les cases adjacentes praticables.

Problème :
Considérez une matrice binaire représentant une carte, où 1 est un chemin praticable et 0 un obstacle. Vous partez de la case en haut à gauche (0, 0) et devez atteindre la case en bas à droite.

Votre tâche :

1. Modélisation : Décrivez comment vous modéliseriez ce problème en termes de graphe. Quels sont les sommets ? Comment définiriez-vous les arêtes (ou la relation de voisinage) ?
2. Algorithme : Adaptez l'algorithme BFS pour résoudre ce problème. Comment gérez-vous les coordonnées (ligne, colonne) ? Comment la condition if v not in visited se traduit-elle ?
3. Trace : Sur une petite grille 3x3 de votre choix avec un obstacle, tracez les premières étapes du BFS : l'état de la file et l'ensemble des cases visitées.

Prenez environ 15 minutes pour réfléchir à ces questions et esquisser une solution sur papier. Il n'est pas nécessaire de coder la solution complète pour cet exercice, l'objectif est de bien maîtriser l'adaptation du modèle.

Conclusion

Aujourd'hui, nous avons ajouté un outil puissant et fondamental à votre arsenal algorithmique : le parcours en largeur.

Points clés à retenir :

• Le BFS explore un graphe couche par couche à l'aide d'une file.
• Sa propriété fondamentale est de trouver le plus court chemin en nombre d'arêtes dans un graphe non pondéré.
• Pour reconstruire le chemin, on utilise un tableau de prédécesseurs.
• Sa complexité, $O(|S|+|A|)$, le rend très efficace, en particulier sur les graphes creux représentés par des listes d'adjacence.
• Le BFS est un algorithme polyvalent qui s'applique à de nombreux problèmes au-delà des graphes explicites, comme les problèmes sur des grilles.

Prochaine étape :
Dans la leçon suivante, nous étudierons le "frère" du BFS : le parcours en profondeur (DFS). Nous verrons qu'en changeant simplement la file pour une pile, nous obtenons un comportement de parcours radicalement différent, avec ses propres applications distinctes comme la détection de cycles ou le tri topologique.