Le parcours de graphes

Les graphes sont l'un des thèmes fédérateurs de l'informatique : une même abstraction décrit les réseaux routiers, les circuits électroniques, les interactions humaines et les réseaux de télécommunication. Formellement, un graphe G = (V, E) est un ensemble de sommets (vertices) V muni d'un ensemble d'arêtes (edges) E, chaque arête étant une paire de sommets. Cette généralité est une source de puissance : une foule de problèmes appliqués, en apparence inextricables, deviennent simples dès qu'on sait les exprimer dans le langage de la théorie des graphes.

Skiena insiste sur un point décisif : concevoir un algorithme de graphe réellement nouveau est très difficile, mais ce n'est presque jamais nécessaire. La vraie compétence consiste à modéliser correctement votre problème pour réutiliser un algorithme existant. Connaître le nom du problème que vous affrontez vaut mieux que maîtriser les détails d'un algorithme particulier. Ce chapitre pose les fondations : le vocabulaire, les deux structures de données canoniques, et les deux parcours — en largeur et en profondeur — sur lesquels reposent la plupart des algorithmes de graphes élémentaires.

Le vocabulaire des graphes

Avant de coder quoi que ce soit, la première étape de tout problème de graphe est d'en identifier la « saveur ». Plusieurs propriétés fondamentales conditionnent à la fois la structure de données et les algorithmes disponibles.

• Orienté ou non orienté (directed / undirected). Un graphe est non orienté si l'arête (x, y) implique toujours l'arête (y, x). Sinon il est orienté. Un réseau routier inter-villes est non orienté ; un plan de rues urbaines, truffé de sens uniques, est orienté ; un graphe de flot d'exécution d'un programme l'est aussi.
• Pondéré ou non pondéré (weighted / unweighted). Dans un graphe pondéré, chaque arête (ou sommet) porte une valeur numérique : longueur, temps de trajet, coût. La distinction est cruciale pour les plus courts chemins : sur un graphe non pondéré, le plus court chemin est celui qui compte le moins d'arêtes, et un parcours en largeur le trouve ; sur un graphe pondéré, il faut des algorithmes plus sophistiqués (chapitre 6).
• Simple ou non simple (simple / non-simple). Une boucle (self-loop) est une arête (x, x). Une multi-arête (multiedge) apparaît plusieurs fois. Un graphe qui évite ces deux structures est dit simple — et nettement plus agréable à manipuler.
• Creux ou dense (sparse / dense). Un graphe est creux quand seule une petite fraction des paires de sommets possibles porte une arête ; dense quand cette fraction est grande. Pas de frontière officielle, mais en pratique un graphe dense a un nombre d'arêtes quadratique et un graphe creux un nombre linéaire. La plupart des graphes réels sont creux : le graphe d'amitié, par exemple — même la personne la plus sociable ne connaît qu'une fraction infime de l'humanité.
• Cyclique ou acyclique (cyclic / acyclic). Un arbre est un graphe non orienté, connexe et acyclique. Un graphe orienté acyclique — un DAG (directed acyclic graph) — apparaît naturellement dans les problèmes d'ordonnancement, où une arête (x, y) signifie « la tâche x doit précéder y ». Le tri topologique est la première opération à mener sur un DAG.
• Étiqueté ou non (labeled / unlabeled). Dans un graphe étiqueté, chaque sommet porte un identifiant unique. Le test d'isomorphisme — déterminer si deux graphes ont la même structure en ignorant les étiquettes — relève typiquement du backtracking.

Deux représentations : matrice ou listes d'adjacence

Le choix de la structure de données a un impact énorme sur les performances. Vos deux options de base sont la matrice d'adjacence et les listes d'adjacence. On note n le nombre de sommets et m le nombre d'arêtes.

La matrice d'adjacence est une matrice n × n où M[i][j] = 1 si l'arête (i, j) existe, 0 sinon. Elle répond instantanément à « l'arête (i, j) existe-t-elle ? » et permet insertion/suppression en O(1). Mais elle gaspille l'espace sur les graphes ayant beaucoup de sommets et peu d'arêtes. Skiena prend l'exemple de Manhattan : une grille d'environ 3 000 carrefours et 6 000 rues. Une matrice d'adjacence aurait 3 000 × 3 000 = 9 000 000 cellules, presque toutes vides.

Les listes d'adjacence stockent, pour chaque sommet, la liste de ses voisins. Elles consomment O(n + m) d'espace et rendent le parcours efficace. Leur faiblesse — vérifier l'existence d'une arête (i, j) impose de parcourir une liste — est rarement gênante : on conçoit presque toujours les algorithmes de graphes pour balayer toutes les arêtes en un seul passage (BFS ou DFS), en traitant chaque arête au moment où on la rencontre, sans jamais poser cette question.

Comparaison	Gagnant
Tester si (x, y) est dans le graphe	matrice — O(1) vs O(d)
Trouver le degré d'un sommet	listes d'adjacence
Moins de mémoire sur petits graphes	listes — O(n + m) vs O(n²)
Moins de mémoire sur graphes denses	matrice (petit avantage)
Insertion / suppression d'arête	matrice — O(1) vs O(d)
Parcourir tout le graphe	listes — Θ(n + m) vs Θ(n²)
Meilleur pour la plupart des problèmes	listes d'adjacence

Voici notre type Graphe en listes d'adjacence, qui servira de socle à tout le chapitre.

// Sommets numérotés de 0 à n-1. Listes d'adjacence.
class Graphe {
  readonly n: number;
  readonly oriente: boolean;
  readonly adj: number[][]; // adj[u] = voisins de u

  constructor(n: number, oriente = false) {
    this.n = n;
    this.oriente = oriente;
    this.adj = Array.from({ length: n }, () => []);
  }

  // O(1) amorti : ajout en fin de liste (l'ordre des voisins n'importe pas).
  ajouterArete(x: number, y: number): void {
    this.adj[x].push(y);
    if (!this.oriente) this.adj[y].push(x);
  }
}

Parcourir un graphe : l'idée des trois états

Le problème le plus fondamental est de visiter chaque sommet et chaque arête de manière systématique. Un graphe modélise naturellement un labyrinthe : les sommets sont les carrefours, les arêtes les couloirs. Tout algorithme de parcours doit être assez robuste pour nous sortir d'un labyrinthe arbitraire — sans se perdre en boucle (efficacité) et sans rien manquer (correction).

L'idée-clé est de marquer chaque sommet dès sa première visite et de tenir à jour ce qui reste à explorer. Chaque sommet passe par trois états successifs :

• non découvert (undiscovered) : état initial, vierge.
• découvert (discovered) : trouvé, mais toutes ses arêtes incidentes ne sont pas encore examinées.
• traité (processed) : toutes ses arêtes incidentes ont été visitées.

On maintient une collection des sommets découverts mais pas encore traités. Quand on explore un sommet v, on examine chacune de ses arêtes sortantes ; si elle mène à un sommet non découvert, on le marque découvert et on l'ajoute au travail à faire. Le seul choix qui distingue les deux parcours est la structure qui stocke ces sommets en attente : une file (FIFO) donne le parcours en largeur, une pile (LIFO) donne le parcours en profondeur.

Le parcours en largeur (BFS)

Le parcours en largeur (breadth-first search, BFS) explore d'abord les sommets les plus anciennement découverts, grâce à une file. Les explorations rayonnent lentement depuis la racine. En assignant à chaque arête une direction, du sommet découvreur u vers le sommet découvert v, on définit u comme le parent de v. Comme chaque sommet a exactement un parent (sauf la racine), cela construit un arbre BFS.

La propriété cruciale : le chemin unique de la racine vers chaque sommet dans l'arbre BFS utilise le plus petit nombre possible d'arêtes. Autrement dit, sur un graphe non pondéré, BFS calcule les plus courts chemins. Il s'exécute en O(n + m), ce qui est optimal : on ne peut pas faire mieux que lire le graphe une fois.

// BFS : distances (en nb d'arêtes) et parents. O(n + m).
function bfs(g: Graphe, source: number): {
  distance: number[];
  parent: number[];
} {
  const distance = Array<number>(g.n).fill(Infinity);
  const parent = Array<number>(g.n).fill(-1);
  const decouvert = Array<boolean>(g.n).fill(false);
  const file: number[] = [source];

  decouvert[source] = true;
  distance[source] = 0;

  for (let tete = 0; tete < file.length; tete++) {
    const u = file[tete]; // défilement O(1) via un index
    for (const v of g.adj[u]) {
      if (!decouvert[v]) {
        decouvert[v] = true;
        distance[v] = distance[u] + 1;
        parent[v] = u;
        file.push(v);
      }
    }
  }
  return { distance, parent };
}

Reconstruire un chemin

Le tableau parent permet de retrouver le plus court chemin. Comme les pointeurs vont de l'enfant vers le parent, on remonte de la cible vers la racine, puis on inverse. La récursion s'en charge élégamment.

// Chemin de la source (racine du BFS) vers `cible`.
function chemin(parent: number[], cible: number): number[] {
  const route: number[] = [];
  for (let v = cible; v !== -1; v = parent[v]) route.push(v);
  return route.reverse();
}

Applications de BFS : composantes connexes et test biparti

La plupart des algorithmes élémentaires effectuent un ou deux parcours en mettant à jour une connaissance du graphe. Bien implémentés sur listes d'adjacence, ils sont linéaires. Deux applications classiques de BFS.

Composantes connexes (connected components). Un graphe est connexe s'il existe un chemin entre toute paire de sommets ; une composante connexe est un ensemble maximal de sommets reliés deux à deux. Un nombre étonnant de problèmes — par exemple « ce Rubik's Cube est-il résoluble depuis cette position ? » — se ramènent à compter des composantes. L'algorithme : lancer un BFS depuis le premier sommet ; tout ce qu'il découvre forme une composante ; recommencer depuis n'importe quel sommet encore non découvert.

// Numéro de composante de chaque sommet. O(n + m).
function composantesConnexes(g: Graphe): number[] {
  const comp = Array<number>(g.n).fill(-1);
  let c = 0;
  for (let depart = 0; depart < g.n; depart++) {
    if (comp[depart] !== -1) continue;
    const file = [depart];
    comp[depart] = c;
    for (let t = 0; t < file.length; t++) {
      for (const v of g.adj[file[t]]) {
        if (comp[v] === -1) {
          comp[v] = c;
          file.push(v);
        }
      }
    }
    c++;
  }
  return comp;
}

Test biparti par 2-coloration (two-coloring). Le problème de coloration de sommets cherche à attribuer une couleur à chaque sommet de sorte qu'aucune arête ne relie deux sommets de même couleur, avec le moins de couleurs possible. Un graphe est biparti s'il se colore sans conflit avec deux couleurs seulement. On augmente le BFS : à chaque sommet découvert, on lui donne la couleur opposée à celle de son parent ; si une arête relie deux sommets déjà de même couleur, le graphe n'est pas biparti.

// Renvoie une 2-coloration, ou null si non biparti. O(n + m).
function estBiparti(g: Graphe): (0 | 1)[] | null {
  const couleur: number[] = Array(g.n).fill(-1);
  for (let depart = 0; depart < g.n; depart++) {
    if (couleur[depart] !== -1) continue;
    couleur[depart] = 0;
    const file = [depart];
    for (let t = 0; t < file.length; t++) {
      const u = file[t];
      for (const v of g.adj[u]) {
        if (couleur[v] === -1) {
          couleur[v] = couleur[u] ^ 1; // couleur opposée
          file.push(v);
        } else if (couleur[v] === couleur[u]) {
          return null; // conflit : pas biparti
        }
      }
    }
  }
  return couleur as (0 | 1)[];
}

Le parcours en profondeur (DFS)

Le parcours en profondeur (depth-first search, DFS) stocke les sommets en attente dans une pile : on s'élance le long d'un chemin, visitant un nouveau voisin dès qu'il en existe un, et ne reculant que lorsqu'on est entouré de sommets déjà découverts. Les explorations s'éloignent vite du point de départ. La pile peut rester implicite : DFS a une élégante implémentation récursive.

La particularité de DFS est qu'il maintient une notion de temps de parcours. Une horloge avance à chaque entrée et chaque sortie de sommet ; on enregistre pour chaque sommet v son temps d'entrée entree[v] et son temps de sortie sortie[v]. Ces intervalles ont des propriétés remarquables :

• Ancêtres et imbrication. Si x est un ancêtre de y dans l'arbre DFS, alors l'intervalle [entree[y], sortie[y]] est strictement imbriqué dans [entree[x], sortie[x]] — on ne peut entrer dans y qu'après x, et en sortir avant x.
• Nombre de descendants. (sortie[v] - entree[v] - 1) / 2 donne le nombre de descendants stricts de v dans l'arbre DFS (et (sortie[v] - entree[v] + 1) / 2 la taille du sous-arbre).

// DFS récursif : temps d'entrée / sortie + parents. O(n + m).
function dfs(g: Graphe): {
  entree: number[];
  sortie: number[];
  parent: number[];
} {
  const entree = Array<number>(g.n).fill(0);
  const sortie = Array<number>(g.n).fill(0);
  const parent = Array<number>(g.n).fill(-1);
  const decouvert = Array<boolean>(g.n).fill(false);
  const traite = Array<boolean>(g.n).fill(false);
  let horloge = 0;

  const explorer = (u: number): void => {
    decouvert[u] = true;
    entree[u] = horloge++;
    for (const v of g.adj[u]) {
      if (!decouvert[v]) {
        parent[v] = u;
        explorer(v); // arête de l'arbre (tree edge)
      }
      // sinon : arête arrière / avant / transverse
    }
    traite[u] = true;
    sortie[u] = horloge++;
  };

  for (let u = 0; u < g.n; u++) if (!decouvert[u]) explorer(u);
  return { entree, sortie, parent };
}

La classification des arêtes

L'autre propriété fondamentale de DFS est qu'il classe les arêtes. Sur un graphe non orienté, il n'existe que deux classes : les arêtes de l'arbre (tree edges), qui découvrent de nouveaux sommets, et les arêtes arrière (back edges), qui pointent vers un ancêtre déjà découvert. Aucune arête ne peut mener à un « frère » ou un « cousin » : tous les sommets atteignables depuis v sont explorés avant qu'on en termine avec v.

Sur un graphe orienté, les quatre cas sont possibles. On les distingue d'après l'état, le temps de découverte et le parent du sommet visé :

arbre (TREE)      : parent[y] == x
arrière (BACK)    : y découvert mais pas encore traité (ancêtre)
avant (FORWARD)   : y traité et entree[y] > entree[x] (descendant)
transverse (CROSS): y traité et entree[y] < entree[x] (autre branche)

Détection de cycles

Les arêtes arrière sont la clé. Dans un graphe non orienté, il y a un cycle si et seulement si DFS rencontre une arête arrière : une arête de x vers un ancêtre y referme un cycle avec le chemin de l'arbre de y à x. S'il n'existe aucune arête arrière, toutes les arêtes appartiennent à l'arbre, et un arbre n'a pas de cycle. Attention au piège : il faut traiter chaque arête non orientée une seule fois, sinon le double parcours d'une même arête fabriquerait un faux cycle (x, y, x) — d'où le test parent[x] !== y.

Tri topologique d'un DAG

Le tri topologique (topological sort) est l'opération la plus importante sur un DAG. Il ordonne les sommets sur une ligne de sorte que toutes les arêtes orientées aillent de gauche à droite. Un tel ordre ne peut exister si le graphe contient un cycle orienté — impossible de toujours avancer vers la droite et de revenir à son point de départ. Tout DAG admet au moins un tri topologique.

Son utilité : il donne un ordre où chaque sommet est traité avant tous ses successeurs. Si les arêtes encodent des contraintes de précédence (« la tâche x avant la tâche y »), tout tri topologique définit un ordonnancement légal. Il sert aussi de première étape à presque tout algorithme sur graphe orienté — par exemple le plus court (ou plus long) chemin dans un DAG, traité en un seul balayage de gauche à droite.

La méthode via DFS est étonnamment simple : étiqueter les sommets dans l'ordre inverse de leur passage à l'état « traité ». Pourquoi ? Quand on explore une arête (x, y) : si y est non découvert, on lance son DFS, donc y est terminé avant x et apparaîtra après lui ; si y est découvert mais non terminé, c'est une arête arrière — interdite dans un DAG ; si y est déjà traité, il a été étiqueté avant x. Dans tous les cas, x précède y.

// Tri topologique d'un DAG via DFS. O(n + m).
// Renvoie null si un cycle orienté est détecté.
function triTopologique(g: Graphe): number[] | null {
  const etat = Array<0 | 1 | 2>(g.n).fill(0); // 0=neuf 1=en cours 2=fini
  const ordre: number[] = [];
  let cycle = false;

  const explorer = (u: number): void => {
    etat[u] = 1;
    for (const v of g.adj[u]) {
      if (etat[v] === 0) explorer(v);
      else if (etat[v] === 1) cycle = true; // arête arrière
    }
    etat[u] = 2;
    ordre.push(u); // empilé une fois toutes ses sorties évaluées
  };

  for (let u = 0; u < g.n && !cycle; u++) {
    if (etat[u] === 0) explorer(u);
  }
  return cycle ? null : ordre.reverse();
}

On empile chaque sommet dès que toutes ses arêtes sortantes ont été évaluées ; le sommet au sommet de la pile n'a jamais d'arête entrante depuis un sommet encore sur la pile. Dépiler répétitivement produit l'ordre.

Un mot sur les composantes fortement connexes

Sur un graphe orienté, la connexité a deux sens. Un graphe est fortement connexe (strongly connected) s'il existe un chemin orienté entre toute paire de sommets — propriété qu'un réseau routier devrait posséder, faute de quoi certains endroits seraient accessibles mais sans retour possible sans violer les sens uniques.

Tester la forte connexité se fait en temps linéaire avec deux parcours : un DFS depuis un sommet v (tous les sommets doivent être atteignables depuis v), puis un DFS depuis v sur le graphe transposé (toutes arêtes inversées), qui vérifie que tous les sommets peuvent atteindre v. Le graphe est fortement connexe si et seulement si les deux conditions sont réunies. Un graphe qui ne l'est pas se partitionne en composantes fortement connexes, identifiables en O(n + m) par une variante de DFS qui suit, pour chaque sommet, le plus vieil ancêtre atteignable via arêtes arrière et transverses — dans le même esprit que la recherche des sommets d'articulation.

À retenir

• Modéliser d'abord, coder ensuite. L'essentiel n'est pas d'inventer un algorithme de graphe, mais de reconnaître le problème classique caché derrière votre cas — connexité, biparti, tri topologique, plus court chemin.
• Listes d'adjacence par défaut. Espace O(n + m), parcours efficace : c'est le bon choix pour la quasi-totalité des applications. La matrice (O(n²)) ne brille que pour tester une arête en O(1) sur des graphes denses.
• BFS pour les plus courts chemins non pondérés. File FIFO, arbre BFS, distances et parents en O(n + m). Applications directes : composantes connexes, test biparti par 2-coloration.
• DFS pour la structure. Pile (souvent récursive), temps d'entrée/sortie, classification des arêtes (arbre, arrière, avant, transverse). C'est cette organisation qui débloque cycles, articulations et composantes fortes.
• Tri topologique d'un DAG. Ordre inverse des sorties de DFS, ou algorithme de Kahn par degrés entrants : dans les deux cas O(n + m), avec détection de cycle gratuite via les arêtes arrière.
• Tout est linéaire ou presque. Bien implémenté sur listes d'adjacence, un parcours coûte O(n + m), soit le minimum pour seulement lire le graphe — ne vous laissez pas piéger par un prétraitement quadratique caché.