Informatique · Algorithmique

Graphes et récursivité

Un plan de métro, un réseau d'amis, les dossiers de ton ordinateur se dessinent avec des points et des traits. Comment un programme les parcourt ?

Déjà à l'aise ? Aller au quiz

Le principe

Un graphe a des sommets (les points) et des arêtes (les traits). Un programme le parcourt : il visite chaque sommet une fois, en suivant les arêtes.

A départ B C D

Chaque sommet n'est visité qu'une fois : c'est tout l'enjeu.

Après cette fiche, tu sais

  • décrire un graphe (sommets, arêtes, orienté, pondéré, cycle, arbre) et le représenter en Java ;
  • dérouler un parcours en largeur (BFS, avec une file) et en profondeur (DFS, avec une pile) ;
  • expliquer pourquoi le BFS trouve le plus court chemin en nombre d'arêtes, et quand il faut Dijkstra ;
  • écrire une fonction récursive correcte (cas de base, cas récursif) et suivre sa pile d'appels ;
  • calculer récursivement la taille ou la hauteur d'un arbre N-aire.
Question à garder en tête : pour aller d'un sommet à un autre en passant par le moins d'arêtes possible, vaut-il mieux explorer en largeur ou en profondeur ?

En largeur, je crois. Mais pourquoi ?

Réponse dans la notion 4, pas à pas. Garde ton intuition en tête : on la vérifie avec une vraie trace.

Des points, des traits, un chemin

Notion 1 · Vocabulaire

Des sommets et des arêtes

Un graphe modélise des relations. Les gares du réseau CFF et les voies qui les relient, des élèves et leurs amitiés, des pages web et leurs liens : tout cela se représente par un graphe.

un cycle (en orange) un arbre : 5 sommets, 4 arêtes

Un cycle revient à son départ ; un arbre n'en a aucun.

Orienté ou non

Une arête orientée (un arc) a un sens, comme un lien web. Une arête non orientée va dans les deux sens, comme une amitié.

A B C D sens : de A vers B dans les deux sens

Chemin et cycle

Un chemin est une suite d'arêtes qui se suivent. Un cycle est un chemin qui revient à son départ : c'est lui qui fait tourner en rond un parcours.

1234 chemin : 1 → 2 → 3 → 4 123 cycle : 1 → 2 → 3 → 1

Degré

Le degré d'un sommet est le nombre d'arêtes qui le touchent. Un élève avec 5 amis a le degré 5.1

élève degré = 5

Arbre

Un arbre est un graphe connexe et sans cycle. Avec n sommets, il a exactement n − 1 arêtes, et un seul chemin relie deux sommets.1

5 sommets, 4 arêtes 4 = 5 − 1

Pondéré

Chaque arête porte un poids : une distance en km, une durée, un coût.

Connexe

Un graphe non orienté est connexe si l'on peut aller de n'importe quel sommet à n'importe quel autre.

Une liste ou une grille

Notion 2 · Représenter

Liste ou matrice d'adjacence

Dans une liste d'adjacence, chaque sommet garde la liste de ses voisins. Dans une matrice d'adjacence, la case (i, j) vaut 1 si une arête relie i et j.

matrice : 3 × 3 012012 010 101 010 liste 0 : [1] 1 : [0, 2] 2 : [1]

Ici, le petit graphe 0 relié à 1, et 1 relié à 2.

Voici le graphe qui sert dans toute la fiche : 10 sommets, 10 arêtes, et un seul cycle (0, 1, 3, 6, 7, 8, 9, 2).

Pour V sommets et E arêtes, les deux représentations se comparent ainsi :

Liste d'adjacenceMatrice d'adjacence
Mémoireproportionnelle à V + EV² cases
« i et j sont-ils voisins ? »parcourir les voisins de iune seule case : immédiat
Parcourir les voisins de iproportionnel au degré de itoujours V cases
Idéale pourles graphes peu denses (la plupart)les graphes denses, les petits graphes
Le graphe de la fiche, en liste d'adjacencejava
List<List<Integer>> adj = List.of(
    List.of(1, 2),     // voisins de 0
    List.of(0, 3, 4),  // voisins de 1
    List.of(0, 5, 9),  // voisins de 2
    List.of(1, 6),     // voisins de 3
    List.of(1), List.of(2), List.of(3, 7),
    List.of(6, 8), List.of(7, 9), List.of(2, 8));

Mémoire

Une liste d'adjacence garde l'essentiel : V + E, soit 10 + 10 = 20 pour ce graphe. Une matrice garde V², soit 10 × 10 = 100 cases, dont beaucoup restent vides.

matrice : V² = 100 cases liste : V + E = 20

Ordre de grandeur

Un réseau social de 10 millions de membres, ayant 200 amis chacun, compte environ 109 arêtes.

109 arêtes

Une liste d'adjacence tient en mémoire. Une matrice de (107)² = 1014 cases, non.

Qui attend son tour

Notion 3 · File et pile

Le moteur des deux parcours

Une file suit la règle FIFO (premier entré, premier sorti), comme une file d'attente. Une pile suit la règle LIFO (dernier entré, premier sorti), comme une pile d'assiettes.3

File (FIFO) 1 2 3 sortie entrée Pile (LIFO) : tout se passe en haut 1 2 3

Le parcours en largeur utilise une file ; le parcours en profondeur, une pile.

Fais défiler : les mêmes éléments, 1, 2, 3 puis 4, entrent dans une file et dans une pile. Leurs ordres de sortie sont opposés.

Scène 1 · File ou pile

Deux structures vides

File (FIFO) sortie entrée Pile (LIFO) : tout se passe en haut SORTIS DE LA FILE rien SORTIS DE LA PILE rien

Exercice · à toi

File ou pile ?

Range chaque situation dans la structure qui la décrit.

Explorer, puis revenir

Notion 4 · Les parcours

En largeur, puis en profondeur

Les deux parcours visitent chaque sommet atteignable une seule fois. Ils ne diffèrent que par la structure qui garde les sommets à traiter. Le parcours en largeur (BFS, breadth-first search) utilise une file.

0 12 3459 6 vague 0vague 1vague 2vague 3

Le BFS range les sommets par vagues de distance depuis le départ.

Fais défiler : il part du sommet 0 et cherche le 9. Chaque vague est traitée entièrement avant la suivante.

Étape 1 sur 7

Départ : la file contient le sommet 0. En pointillé orange, la cible : 9.

Étape 2 sur 7 · vague 1

On retire 0 et on ajoute ses voisins 1 et 2 : ils sont à 1 arête. File : [1, 2].

Étape 3 sur 7

On retire le plus ancien, 1, et on ajoute 3 et 4. File : [2, 3, 4].

Étape 4 sur 7 · vague 2

On retire 2 : 5 et 9 entrent. La cible est découverte à 2 arêtes, et son parent est 2.

Étape 5 sur 7

3 sort (6 entre), puis 4 et 5. Vient le tour de 9 : c'est la cible, on s'arrête.

Étape 6 sur 7 · le chemin

On remonte les parents : 9 vient de 2, qui vient de 0. Chemin 0 → 2 → 9 : 2 arêtes.

Étape 7 sur 7 · et le DFS ?

En profondeur, on file par 1, 3, 6, 7 et 8 : 6 arêtes. Un chemin, pas le plus court.

Réponse à ma question : en largeur. Le BFS traite tous les sommets à 1 arête, puis tous ceux à 2 arêtes, et ainsi de suite. Aucun sommet ne peut être atteint avant sa vague : le premier chemin trouvé est le plus court.1

Le BFS en Java : une file et des parents

Parcours en largeur jusqu'à une ciblejava
static List<Integer> bfs(int depart, int cible) {
    int[] parent = new int[adj.size()];
    Arrays.fill(parent, -1);
    boolean[] vu = new boolean[adj.size()];
    Deque<Integer> file = new ArrayDeque<>();
    file.add(depart);
    vu[depart] = true;
    while (!file.isEmpty()) {
        int s = file.poll();                  // le plus ancien (FIFO)
        if (s == cible) return chemin(parent, cible);
        for (int v : adj.get(s)) {
            if (!vu[v]) { vu[v] = true; parent[v] = s; file.add(v); }
        }
    }
    return List.of();                         // cible inatteignable
}

Le parcours en profondeur (DFS, depth-first search) s'écrit le plus simplement en récursif : la pile, c'est la pile d'appels de Java. Version complète, sans cible, pour visiter tout le graphe :

Parcours en profondeur completjava
static void parcours(int s, boolean[] vu) {
    vu[s] = true;                        // s est visité
    for (int v : adj.get(s)) {
        if (!vu[v]) parcours(v, vu);     // on descend
    }
}                                        // fin : retour en arrière

Fais défiler : chaque appel empile un cadre, chaque fin d'appel le dépile.

parcours(0) parcours(1) parcours(3) le cadre du haut est l'appel en cours chaque fin d'appel dépile le sien
Scène 2 · Le DFS et sa pile d'appels

Avant le premier appel

profondeur 0visités aucun

Tu as vu ? Pendant la descente, la pile d'appels contient exactement le chemin suivi depuis 0. Quand un appel se termine, on recule d'un pas : c'est le retour en arrière, le « backtracking ».

Coût

Avec une liste d'adjacence, chaque parcours coûte un temps proportionnel à V + E : chaque sommet est traité une fois, chaque arête examinée une ou deux fois.1

BFS

BFS traite les sommets par distance croissante au départ : il donne le plus court chemin en nombre d'arêtes (graphe non pondéré). Exemple : les degrés de séparation dans un réseau social.

DFS

DFS va le plus loin possible puis revient en arrière : utile pour tester si un graphe est connexe, détecter un cycle, faire un tri topologique ou explorer un labyrinthe avec un fil d'Ariane.

Le tableau vu

Sans le tableau vu, un parcours tournerait en rond sur le moindre cycle.

Exercice · à toi

Suis le parcours

Trois questions sur le graphe de la fiche. Les réponses ont été vérifiées en exécutant le code Java.

Une fonction qui s'appelle elle-même

Notion 5 · La récursivité

Une fonction qui s'appelle elle-même

Une fonction récursive résout un problème en s'appelant sur un problème plus petit. Elle a deux parties : un cas de base, qui répond sans nouvel appel, et un cas récursif, qui rapproche du cas de base.4

fact(n) = n × fact(n − 1)cas de base : fact(0) = fact(1) = 1

fact(4) fact(3) fact(2) fact(1) = 1 = 2 = 6 = 24 on descend par appels, on remonte par résultats
Factoriellejava
static int fact(int n) {
    if (n <= 1) return 1;           // cas de base (fact(0) = fact(1) = 1)
    return n * fact(n - 1);         // cas récursif
}

Chaque appel empile un cadre sur la pile d'appels : ses paramètres, ses variables locales, l'endroit où reprendre. Les cadres se dépilent ensuite dans l'ordre inverse, en rendant leur résultat. Fais défiler.

fact(4) fact(3) fact(2) fact(1) 4 cadres en même temps
Scène 3 · fact(4)

Avant l'appel

Appel : fact(4) static int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); } fact(4) = 24 Profondeur de pile : 0 pile d'appels

Si le cas de base n'est jamais atteint, la pile finit par déborder : Java lève une StackOverflowError.5

34 661

appels avant le débordement, sur l'ordinateur qui a servi à vérifier cette fiche.

Sans cas de base, les cadres s'empilent jusqu'à remplir la pile. Sur l'ordinateur qui a servi à vérifier cette fiche, Java a levé une StackOverflowError après 34 661 appels.

Récursif ou itératif ?

Tout calcul récursif peut s'écrire avec une boucle (et, au besoin, une pile explicite). Le récursif est plus lisible pour les structures récursives, comme les arbres ou le parcours en profondeur.

boucle i une seule case récursion une pile qui grandit

L'itératif évite le débordement de pile quand la profondeur peut devenir très grande. Java n'optimise pas la récursion terminale : une fonction dont l'appel récursif est la dernière instruction déborde elle aussi (vérifié avec une profondeur d'un million).

Exercice · à toi

Que renvoie cette fonction ?

Déroule les appels sur une feuille avant de répondre. Les trois fonctions ont été exécutées en Java 21.

Un dossier dans un dossier

Notion 6 · Les arbres N-aires

Une structure récursive par nature

Dans un arbre N-aire, chaque nœud a un nombre quelconque d'enfants : un dossier et ses sous-dossiers, un organigramme, le DOM d'une page web.

cours2 Mo maths10 Mo exos5 Mo info3 Mo

Un arbre, c'est un nœud et une liste de sous-arbres : les algorithmes récursifs s'y écrivent naturellement.

Taille et hauteur d'un arbre de dossiersjava
record Noeud(String nom, int taille, List<Noeud> enfants) {}

static int tailleTotale(Noeud n) {        // parcours postfixe
    int total = n.taille();
    for (Noeud e : n.enfants()) total += tailleTotale(e);
    return total;
}

static int hauteur(Noeud n) {             // une feuille a la hauteur 0
    int h = 0;
    for (Noeud e : n.enfants()) h = Math.max(h, 1 + hauteur(e));
    return h;
}

Fais défiler : tailleTotale sur un dossier « cours » de 2 Mo, qui contient « maths » (10 Mo, avec un sous-dossier « exos » de 5 Mo) et « info » (3 Mo).

PILE D'APPELS vide
Étape 1 sur 5

tailleTotale(cours) commence : total = 2, puis la boucle appelle le premier enfant, maths.

Étape 2 sur 5

tailleTotale(maths) : total = 10, puis appel sur exos. Trois cadres sur la pile : la hauteur plus un.

Étape 3 sur 5

exos n'a pas d'enfant : la boucle ne fait rien, il renvoie 5. C'est le cas de base, implicite.

Étape 4 sur 5

maths renvoie 10 + 5 = 15. Puis cours appelle info, une feuille, qui renvoie 3.

Étape 5 sur 5

cours renvoie 2 + 15 + 3 = 20 Mo. Sa hauteur vaut 2 : le chemin cours, maths, exos.

Préfixe ou postfixe

Le cas de base est implicite : une feuille n'a pas d'enfant, la boucle ne fait rien. Un parcours préfixe traite le nœud avant ses enfants (afficher une arborescence) ; un parcours postfixe après eux.

préfixe : le nœud avant ses enfants cours maths exos info postfixe : les enfants avant le nœud exos maths info cours

Pour additionner les tailles, comme ici, la valeur d'un dossier ne sort qu'une fois celles de ses enfants connues. La hauteur d'une feuille vaut 0 ; celle d'un dossier, 1 + la plus grande hauteur de ses enfants.

Sur un arbre de hauteur h, la pile d'appels contient au plus h + 1 cadres.

Des routes qui ont une longueur

Notion 7 · Graphes pondérés

Quand les arêtes ont une longueur : Dijkstra

Le BFS compte des arêtes, pas des kilomètres. Sur le dessin, il choisit la route directe (1 arête, 10 km) alors que le détour par C ne fait que 7 km.

BFS : A → B, 1 arête, 10 km Dijkstra : A → C → B, 2 arêtes, 7 km 10 km3 km4 km ABC

Pour le plus court chemin dans un graphe pondéré, on utilise l'algorithme de Dijkstra : il traite toujours le sommet non traité le plus proche du départ, grâce à une file de priorité, et met à jour les distances de ses voisins.

1. Le plus proche : A, à 0 km. 2. Le plus proche non traité : C, à 3 km. 3. B : 7 km par C (3 + 4), contre 10 km en direct.

Il exige des poids positifs ou nuls ; son coût est proportionnel à E log V avec un tas binaire.2 Avec des poids négatifs, on passe à l'algorithme de Bellman-Ford.

La variante A* ajoute à la distance parcourue une estimation de la distance restante jusqu'à la cible, pour explorer d'abord dans la bonne direction.6

Pièges, puis entraînement

Attention

Les pièges classiques

Oublier de marquer les sommets visités

Sur un graphe avec un cycle, le parcours revient sans fin sur ses pas. En BFS, on marque un sommet au moment où il entre dans la file, pas quand il en sort.

Croire que le DFS donne le plus court chemin

Sur le graphe de la fiche, il trouve 6 arêtes là où le BFS en trouve 2.

Utiliser le BFS sur un graphe pondéré

Deux petites routes peuvent être plus courtes qu'une longue route directe : il faut Dijkstra.

Un cas de base trop étroit

Avec if (n == 1) return 1;, fact(0) appelle fact(-1), puis fact(-2)… jusqu'au StackOverflowError. Écris n <= 1.

Un appel récursif qui ne rapproche pas du cas de base

return n * fact(n) ne diminue jamais n : récursion infinie.

Choisir une matrice pour un grand graphe peu dense

V² cases pour quelques arêtes par sommet : la liste d'adjacence est bien plus économe.

Entraîne-toi

Exercices corrigés

Cherche d'abord, puis ouvre le corrigé. Les réponses ont été vérifiées en exécutant le code Java de la fiche.

1Sur le graphe de la fiche, donne l'ordre de visite du BFS depuis 0 jusqu'à ce que 9 sorte de la file, puis celui du DFS vers 9 (voisins pris dans l'ordre croissant).Voir le corrigé

BFS : 0, 1, 2, 3, 4, 5, 9 (la file vaut [1, 2], puis [2, 3, 4], puis [3, 4, 5, 9], puis [4, 5, 9, 6]…). DFS : 0, 1, 3, 6, 7, 8, 9 : il file par 1 et n'atteint jamais 2 avant la cible.

2Écris une fonction récursive somme(int[] t, int i) qui additionne les éléments de t à partir de l'indice i. Que vaut somme(new int[]{4, 5, 6}, 0) ?Voir le corrigé
static int somme(int[] t, int i) {
    if (i == t.length) return 0;      // plus rien à additionner
    return t[i] + somme(t, i + 1);
}

Déroulé : 4 + (5 + (6 + 0)) = 15.

3Un graphe non orienté a 1000 sommets et 3000 arêtes. Combien de cases faut-il pour une matrice d'adjacence ? Et combien d'entrées de voisins pour une liste d'adjacence ?Voir le corrigé

Matrice : 1000² = 1 000 000 cases. Liste : chaque arête apparaît deux fois (chez ses deux extrémités), soit 6000 entrées, plus 1000 listes. La liste est plus de cent fois plus économe ici.

4On ajoute un dossier « images » de 8 Mo dans « info ». Que renvoient maintenant tailleTotale(cours) et hauteur(cours) ?Voir le corrigé

Taille : 2 + (10 + 5) + (3 + 8) = 28 Mo. Hauteur : toujours 2, car « images » est à la même profondeur que « exos ».

À retenir

La fiche en huit lignes

Graphesommets et arêtes ; orienté ou non, pondéré ou non ; arbre = connexe sans cycle.
Représentationliste d'adjacence (V + E), matrice (V²).
File et pileFIFO : le plus ancien sort ; LIFO : le dernier entré sort.
BFSune file ; plus court chemin en nombre d'arêtes ; temps V + E.
DFSune pile ou la récursion ; retour en arrière ; un chemin, pas forcément le plus court.
Récursivitécas de base + appel qui s'en rapproche ; chaque appel empile un cadre.
Arbres N-airestaille et hauteur se calculent récursivement ; pile ≤ hauteur + 1 cadres.
Dijkstragraphes pondérés, poids ≥ 0, file de priorité, E log V ; A* ajoute une estimation.

Douze questions pour finir

Dernière étape, le quiz. Si tu hésites sur un parcours, dessine la file ou la pile à côté du graphe, étape par étape.
Quiz final

Teste-toi

Sources

  1. Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, section 4.1 « Undirected Graphs » (degré, arbre, BFS et plus court chemin en nombre d'arêtes, temps proportionnel à V + E) et section 4.3 « Minimum Spanning Trees » (propriétés des arbres ; un arbre couvrant de V sommets se construit avec V − 1 arêtes), consulté le 8 octobre 2026. 4.1, 4.3 (algs4.cs.princeton.edu)
  2. Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, section 4.4 « Shortest Paths » (Dijkstra avec poids positifs ou nuls, temps E log V ; Bellman-Ford pour les poids négatifs), consulté le 8 octobre 2026. algs4.cs.princeton.edu
  3. Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, section 1.3 « Bags, Queues, and Stacks » (file FIFO, pile LIFO), consulté le 8 octobre 2026. algs4.cs.princeton.edu
  4. Robert Sedgewick, Kevin Wayne, Computer Science: An Interdisciplinary Approach, section 2.3 « Recursion » (cas de base, étape de réduction, StackOverflowError), consulté le 8 octobre 2026. introcs.cs.princeton.edu
  5. Oracle, StackOverflowError (Java SE 25 & JDK 25) (« Thrown when a stack overflow occurs because an application recurses too deeply »), consulté le 8 octobre 2026. docs.oracle.com
  6. Amit Patel, Introduction to A*, Amit’s Thoughts on Pathfinding (A* trouve un plus court chemin comme Dijkstra, guidé par une estimation h(n) du coût restant : f(n) = g(n) + h(n)), consulté le 8 octobre 2026. theory.stanford.edu

Fiche relue et sourcée en septembre 2026, refaite en récit en octobre 2026. Code Java compilé et exécuté avec Java 21 : ordres de visite du BFS, du DFS et du parcours complet, chemins, fact, somme, taille et hauteur, fonctions des exercices ; StackOverflowError après 34 661 appels sans cas de base, et pour une récursion terminale de profondeur 1 000 000.

Glisser pour continuer vers Les bases de JavaScript
Université