Parcours de graphes : BFS et DFS

En 1736, Leonhard Euler a montré qu'aucune promenade ne traverse chacun des sept ponts de Königsberg exactement une fois, et la théorie des graphes est née de cette réponse.

Des points et des traits

Un graphe est un ensemble de points, appelés sommets ou nœuds, reliés par des traits, appelés arêtes. L'idée est simple, et elle s'applique à une foule de choses : des villes reliées par des routes, des pages web reliées par des liens, des personnes reliées par des amitiés, les cases d'un labyrinthe reliées là où il n'y a pas de mur. Une fois qu'un problème est dessiné sous forme de graphe, la même poignée d'algorithmes peut répondre à des questions comme « puis-je aller d'ici à là ? » et « quel est le chemin le plus court ? »

Stocker un graphe dans du code

Une façon courante de stocker un graphe est la liste d'adjacence : pour chaque sommet, la liste de ses voisins. Les notes du cours 6.006 du MIT utilisent exactement cela, un tableau ou dictionnaire Adj où Adj[u] liste les sommets reliés à u. Pour le graphe ci-dessus, cela donne :

const graph = {   // liste d'adjacence
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

Le parcours en largeur : anneau par anneau

Le parcours en largeur (BFS, breadth-first search) explore un graphe par anneaux autour du départ. D'abord le départ lui-même, à distance 0. Puis tous ses voisins, à distance 1. Puis chaque nouveau sommet voisin de ceux-là, à distance 2, et ainsi de suite. Pour cela, il utilise une file, une file d'attente où le premier entré est le premier sorti. On prend le sommet en tête de file, on le visite et on ajoute ses voisins pas encore vus en queue de file. À partir de A dans l'exemple, le BFS visite A, puis B et C, puis D et E, puis F. Comme il avance d'un anneau à la fois, la première fois que le BFS atteint un sommet, il a trouvé un chemin avec le moins d'arêtes possible. F est à 3 arêtes de A, par exemple A, B, D, F.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // premier entré, premier sorti
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

Le parcours en profondeur : aussi loin que possible, puis retour en arrière

Le parcours en profondeur (DFS, depth-first search) se comporte comme une personne qui garde une main sur le mur dans un labyrinthe. Il suit un chemin aussi loin que possible. Quand il arrive à une impasse ou à un endroit déjà vu, il revient au dernier embranchement et essaie l'option suivante. Il utilise une pile au lieu d'une file, dernier entré, premier sorti, et il s'écrit très naturellement avec la récursivité, où la pile d'appels se charge de se souvenir. À partir de A, un DFS récursif visite A, B, D, C, E, F. Le DFS atteint tous les sommets que le BFS atteint, mais le chemin qu'il suit n'est pas forcément le plus court.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // A B D C E F (en profondeur)
}

Lequel utiliser

Dans le premier labyrinthe du labo, le BFS visite 105 cases et trouve un chemin de 22 déplacements, le plus court possible. Le DFS plonge par chance vers l'arrivée et ne visite que 31 cases, mais son chemin demande 28 déplacements. Aucun n'est toujours moins coûteux. Les deux traitent chaque sommet et chaque arête un nombre fixe de fois : tous deux s'exécutent donc en temps O(V + E) pour V sommets et E arêtes. Choisis le BFS quand il te faut le moins d'étapes : le moins de coups dans un casse-tête, le moins de liens entre deux personnes. Choisis le DFS quand il faut tout explorer ou suivre des choix jusqu'au bout : vérifier que toutes les pièces d'un labyrinthe communiquent, ou essayer les coups d'un casse-tête une ligne à la fois en revenant en arrière quand on est bloqué. Quand les arêtes ont des longueurs différentes, comme les routes, aucun des deux ne suffit seul ; des méthodes comme l'algorithme de Dijkstra prolongent l'idée du BFS avec des distances.