Visualiseur BFS en Ligne

Pseudocode

Tout l'algorithme tient dans une file et un ensemble de sommets visités. Toutes les autres propriétés qui font la réputation du BFS découlent de l'ordre dans lequel la file restitue les sommets.

BFS(graphe, source):
    visites = {source}
    dist[source] = 0
    file = [source]

    tant que la file est non vide:
        u = file.retirerPremier()
        pour chaque voisin v de u:
            si v absent de visites:
                visites.ajouter(v)
                dist[v] = dist[u] + 1
                parent[v] = u
                file.ajouterEnFin(v)

L'invariant est que la file contient toujours des sommets appartenant à au plus deux niveaux de distance consécutifs, en ordre croissant au sens large. Cette seule propriété rend dist correct: un sommet reçoit sa distance la première fois qu'il est vu, et il ne peut plus être atteint à moindre coût par la suite.

Exemple détaillé, étape par étape

Exécute BFS depuis A sur le graphe chargé par défaut dans le visualiseur, afin de suivre chaque étape dans le panneau ci-dessus.

Graphe d'exemple: Arêtes non orientées A-B (2), A-C (3), B-C (1) et C-D (4). BFS ignore totalement les poids et compte les sauts, chaque arête vaut donc un.

1. Départ. Marque A comme visité avec dist 0 et place-le dans la file. File: [A].
2. Défiler A. A a pour voisins B et C, aucun visité. Tous deux reçoivent dist 1 et parent A. File: [B, C].
3. Défiler B. B a pour voisins A et C. Les deux sont déjà visités: A comme source, C revendiqué un instant plus tôt par A. Rien n'est ajouté. Cette étape montre pourquoi BFS ne repasse jamais: atteindre C via B coûterait 2 sauts contre le 1 déjà enregistré. File: [C].
4. Défiler C. C a pour voisins A, B et D. Seul D est nouveau, il reçoit donc dist 2 et parent C. File: [D].
5. Défiler D. Le seul voisin de D est C, déjà visité. La file se vide et la recherche se termine.

Les distances finales sont A 0, B 1, C 1, D 2, et les pointeurs parents donnent l'arbre des plus courts chemins A vers B, A vers C et C vers D. Remarque que BFS atteint D en passant par C alors que le coût pondéré de ce trajet vaut 7 contre 3 pour A vers B vers C: la seule chose optimisée est le nombre de sauts, ce qui explique précisément pourquoi les graphes pondérés exigent Dijkstra.

Complexité et son origine

Temps: O(V + E) · Espace: O(V)

Chaque sommet entre dans la file au plus une fois, parce qu'il est marqué visité au moment de l'enfilement et non du défilement. Cela borne la boucle externe à V itérations. À l'intérieur, le travail est proportionnel au degré du sommet courant, et la somme de tous les degrés vaut 2E dans un graphe non orienté, donc le parcours des voisins totalise O(E). L'espace est dominé par l'ensemble des visités, le tableau des distances et la file, chacun en O(V). Avec une matrice d'adjacence, le parcours des voisins coûte O(V) par sommet et l'exécution complète se dégrade en O(V au carré).

Quand utiliser Recherche en Largeur (BFS), et quand l'éviter

BFS est le choix par défaut tant que les arêtes ne sont pas pondérées. Dès que des poids apparaissent, ou que l'objectif passe de la distance à la structure, autre chose l'emporte.

Pièges fréquents

• Marquer visité au défilement plutôt qu à l enfilement. Si un sommet n'est marqué qu'en sortant de la file, il peut y entrer de nombreuses fois avant son premier défilement. Sur les graphes denses, cela transforme un parcours linéaire en parcours quadratique et peut épuiser la mémoire. Marque-le au moment où tu l'empiles.
• Utiliser BFS sur un graphe pondéré. BFS compte les sauts, pas le poids. Dans un graphe où A vers C coûte 100 en une arête et A vers B vers C coûte 2 en deux arêtes, BFS annonce que le trajet à 100 est le plus court. Prends Dijkstra à la place.
• Reconstruire le chemin à partir des seules distances. Les distances disent à quelle distance, pas par où. Enregistre un pointeur parent au moment d'affecter une distance, puis remonte les parents depuis la cible et inverse le résultat.
• Utiliser la récursion au lieu d une file. Un parcours récursif est en profondeur, quel que soit son nom. BFS exige une file FIFO explicite; il n'existe pas de formulation récursive naturelle.

Questions fréquentes

À quoi sert le parcours en largeur?

BFS trouve le plus court chemin dans les graphes non pondérés, teste la connexité et la bipartition, et parcourt les arbres niveau par niveau. C'est aussi la recherche de chemins augmentants au cœur d'Edmonds-Karp pour le flot maximal, et il sous-tend les requêtes de distance minimale dans les réseaux sociaux et de routage.

Quelle est la complexité temporelle du BFS?

O(V + E) en temps et O(V) en espace avec une liste d'adjacence, où V est le nombre de sommets et E celui des arêtes. Avec une matrice d'adjacence, cela devient O(V au carré), car chaque parcours de voisins coûte O(V) indépendamment du degré réel.

Le BFS trouve-t-il toujours le plus court chemin?

Oui sur les graphes non pondérés, non sur les graphes pondérés. BFS développe les sommets par nombre de sauts croissant au sens large, donc la première fois qu'il atteint un sommet, il a utilisé le minimum d'arêtes possible. Dès que les arêtes portent des poids différents, cette garantie tombe, car le moins d'arêtes et le poids total le plus faible cessent de coïncider.

Quelle est la différence entre BFS et DFS?

BFS explore niveau par niveau avec une file et trouve les plus courts chemins dans les graphes non pondérés. DFS suit une branche jusqu'au bout avec une pile ou la récursion et révèle la structure: cycles, tri topologique, composantes fortement connexes. BFS consomme plus de mémoire sur les graphes larges, DFS sur les graphes profonds.

Le BFS peut-il détecter un cycle?

Oui. Dans un graphe non orienté, si BFS atteint un sommet déjà visité qui n'est pas le parent du sommet courant, cette arête ferme un cycle. Dans un graphe orienté, BFS convient mal et l'usage est le tri topologique de Kahn ou un DFS avec classification des arêtes.