BFS (Breadth-First Search)

Le concept du jour : le BFS (Breadth-First Search), ou parcours en largeur. Contrairement à son cousin le DFS qui fonce tête baissée vers le fond, le BFS est prudent : il explore par "vagues" ou par "étages". Il scanne tout ce qui est proche avant de s'éloigner. C'est l'algorithme qu'on convoque quand on cherche le chemin le plus court.

Le principe : l'exploration en largeur, par niveaux

Imaginez une pierre jetée dans un lac. Les ondes se propagent en cercles concentriques, du centre vers l'extérieur. Le BFS fonctionne exactement ainsi : depuis un nœud de départ, il visite d'abord tous ses voisins directs (niveau 1), puis tous les voisins de ces voisins (niveau 2), et ainsi de suite jusqu'à avoir tout couvert.

Prenons le même graphe que pour le DFS :

A -- B -- D
|    |
C    E

Depuis A, le BFS visitera dans cet ordre : A → B, C (voisins de A, niveau 1) → D, E (voisins de B, niveau 2). Jamais il ne s'aventure au niveau 2 avant d'avoir fini le niveau 1.

Cette propriété est fondamentale : le BFS garantit que le premier chemin trouvé vers un nœud est le plus court (en nombre d'arêtes). C'est ce qui le distingue du DFS et ce qui lui confère une valeur pratique immense.

BFS vs DFS : deux philosophies d'exploration

Le DFS est un explorateur intrépide qui fonce dans un couloir sans regarder en arrière. Le BFS est un stratège méthodique qui cartographie le terrain autour de lui avant d'avancer. Ni l'un ni l'autre n'est supérieur : tout dépend du problème à résoudre.

Comment ça marche : la file FIFO

La différence structurelle fondamentale entre BFS et DFS tient en un seul mot : file (queue) vs pile (stack).

Le DFS utilise une pile (implicitement via la récursion) : on empile les nœuds à explorer, et on traite toujours le dernier arrivé en premier. Résultat : on plonge en profondeur.

Le BFS utilise une file FIFO (First In, First Out) : on enfile les nœuds à explorer, et on traite toujours le premier arrivé en premier. Résultat : on explore niveau par niveau.

L'algorithme se déroule ainsi :

1. On enfile le nœud de départ et on le marque comme visité.
2. Tant que la file n'est pas vide :
   • On défile le premier nœud.
   • On traite ce nœud (affichage, vérification, etc.).
   • Pour chaque voisin non encore visité, on le marque visité et on l'enfile.
3. La file se vide quand tout le graphe accessible a été parcouru.

Le marquage des nœuds comme visités avant de les enfilement (et non après les avoir traités) est crucial pour éviter d'envoyer le même nœud plusieurs fois dans la file.

Implémentation TypeScript

// Représentation du graphe : chaque nœud pointe vers ses voisins
type Graph = Map<string, string[]>;
 
function bfs(graph: Graph, start: string): void {
  const visited = new Set<string>();
  const queue: string[] = [];
 
  // On initialise avec le nœud de départ
  visited.add(start);
  queue.push(start);
 
  while (queue.length > 0) {
    // On défile le premier nœud (FIFO)
    const node = queue.shift()!;
    console.log(node);
 
    // On enfile tous les voisins non visités
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}
 
// Exemple d'utilisation
const graph: Graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["D", "E"]],
  ["C", []],
  ["D", []],
  ["E", []],
]);
 
bfs(graph, "A");
// Affiche : A, B, C, D, E

Trouver le plus court chemin

C'est le cas d'usage phare du BFS. On adapte légèrement l'implémentation pour mémoriser le chemin parcouru :

function shortestPath(
  graph: Graph,
  start: string,
  end: string
): string[] | null {
  if (start === end) return [start];
 
  const visited = new Set<string>();
  // On stocke le nœud précédent pour reconstruire le chemin
  const previous = new Map<string, string>();
  const queue: string[] = [];
 
  visited.add(start);
  queue.push(start);
 
  while (queue.length > 0) {
    const node = queue.shift()!;
 
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        previous.set(neighbor, node);
        queue.push(neighbor);
 
        // Dès qu'on atteint la destination, on reconstruit le chemin
        if (neighbor === end) {
          const path: string[] = [];
          let current: string = end;
 
          while (current !== start) {
            path.unshift(current);
            current = previous.get(current)!;
          }
          path.unshift(start);
 
          return path;
        }
      }
    }
  }
 
  // Pas de chemin trouvé
  return null;
}
 
const graph: Graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["D", "E"]],
  ["C", ["F"]],
  ["D", []],
  ["E", ["F"]],
  ["F", []],
]);
 
console.log(shortestPath(graph, "A", "F"));
// Affiche : ["A", "C", "F"] — 2 arêtes, le plus court chemin

Cas d'usage concrets

Plus court chemin dans un graphe non pondéré : c'est le cas d'école. Un réseau routier où toutes les routes ont le même coût, un jeu de plateau où chaque déplacement compte pour un, une grille 2D — dans tous ces contextes, le BFS trouve le chemin optimal. Pour des graphes pondérés (avec des distances variables), on préférera l'algorithme de Dijkstra.

Degrés de séparation dans les réseaux sociaux : la théorie des "six degrés de séparation" dit que n'importe quelle personne sur Terre est connectée à n'importe quelle autre par une chaîne de six relations au maximum. Trouver le degré de séparation entre deux utilisateurs sur LinkedIn ou Facebook, c'est un BFS classique sur le graphe social. LinkedIn utilise exactement ce principe pour afficher "relation au 2e degré".

Web crawling : un crawler qui explore le web depuis une URL de départ peut utiliser le BFS pour explorer les pages par proximité. On commence par scraper la page de départ, on extrait tous ses liens (niveau 1), puis tous les liens de ces pages (niveau 2), etc. Le BFS garantit qu'on explore d'abord les pages les plus proches de l'origine, ce qui est utile pour indexer en priorité le contenu pertinent.

Résolution de puzzles par niveaux : le jeu du taquin (sliding puzzle), le Rubik's Cube, Word Ladder (passer d'un mot à un autre en changeant une lettre à la fois) — tous ces problèmes peuvent être modélisés comme un graphe d'états, et le BFS trouve la solution en un nombre minimal d'étapes.

Détection de composantes connexes : comme le DFS, le BFS peut identifier les "îlots" disconnectés dans un graphe. On lance un BFS depuis chaque nœud non encore visité et on incrémente un compteur de composantes à chaque nouveau départ.

Complexité

• Temps : O(V + E) — on visite chaque sommet (Vertex) une fois et on parcourt chaque arête (Edge) une fois. Identique au DFS.
• Espace : O(V) dans le pire cas, pour la file et l'ensemble des nœuds visités.

La nuance importante sur la mémoire : dans un graphe très "large" (beaucoup de voisins à chaque niveau), la file du BFS peut devenir volumineuse. Dans un graphe très "profond" (longues chaînes linéaires), c'est la pile du DFS qui gonfle. La topologie du graphe détermine lequel des deux algorithmes consomme moins de mémoire en pratique.

Un mot sur queue.shift()

Dans l'implémentation ci-dessus, on utilise queue.shift() pour retirer le premier élément du tableau. En JavaScript, cette opération est O(n) car elle réindexe tout le tableau. Pour un BFS sur un très grand graphe, cela peut devenir un goulot d'étranglement.

La solution propre est d'utiliser une vraie structure de file avec un pointeur de tête :

class Queue<T> {
  private items: T[] = [];
  private head = 0;
 
  enqueue(item: T): void {
    this.items.push(item);
  }
 
  dequeue(): T | undefined {
    if (this.head >= this.items.length) return undefined;
    return this.items[this.head++];
  }
 
  get size(): number {
    return this.items.length - this.head;
  }
}

Avec cette implémentation, dequeue() est O(1) : on déplace juste un pointeur plutôt que de réindexer le tableau. Un détail qui change tout à grande échelle.

Le BFS est l'un des algorithmes les plus fondamentaux de l'informatique. Sa logique par vagues, sa garantie du plus court chemin, et son omniprésence dans les systèmes réels (GPS, réseaux sociaux, moteurs de recherche) en font un incontournable à maîtriser. Savoir quand choisir BFS plutôt que DFS — et pourquoi — c'est la marque d'un développeur qui comprend ses outils.