Pondéré
Chaque arête porte un poids : une distance en km, une durée, un coût.
Informatique · Algorithmique
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 quizLe 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.
Chaque sommet n'est visité qu'une fois : c'est tout l'enjeu.
Après cette fiche, tu sais
Le plan
En largeur, je crois. Mais pourquoi ?
Des points, des traits, un chemin
Notion 1 · Vocabulaire
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 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é.
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.
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
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
Chaque arête porte un poids : une distance en km, une durée, un coût.
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
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.
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'adjacence | Matrice d'adjacence | |
|---|---|---|
| Mémoire | proportionnelle à V + E | V² cases |
| « i et j sont-ils voisins ? » | parcourir les voisins de i | une seule case : immédiat |
| Parcourir les voisins de i | proportionnel au degré de i | toujours V cases |
| Idéale pour | les graphes peu denses (la plupart) | les graphes denses, les petits graphes |
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.
Ordre de grandeur
Un réseau social de 10 millions de membres, ayant 200 amis chacun, compte environ 109 arêtes.
109 arêtesUne liste d'adjacence tient en mémoire. Une matrice de (107)² = 1014 cases, non.
Qui attend son tour
Notion 3 · File et pile
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
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.
Deux structures vides
Range chaque situation dans la structure qui la décrit.
Explorer, puis revenir
Notion 4 · Les parcours
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.
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.
Départ : la file contient le sommet 0. En pointillé orange, la cible : 9.
On retire 0 et on ajoute ses voisins 1 et 2 : ils sont à 1 arête. File : [1, 2].
On retire le plus ancien, 1, et on ajoute 3 et 4. File : [2, 3, 4].
On retire 2 : 5 et 9 entrent. La cible est découverte à 2 arêtes, et son parent est 2.
3 sort (6 entre), puis 4 et 5. Vient le tour de 9 : c'est la cible, on s'arrête.
On remonte les parents : 9 vient de 2, qui vient de 0. Chemin 0 → 2 → 9 : 2 arêtes.
En profondeur, on file par 1, 3, 6, 7 et 8 : 6 arêtes. Un chemin, pas le plus court.
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 :
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èreFais défiler : chaque appel empile un cadre, chaque fin d'appel le dépile.
Avant le premier appel
profondeur 0visités aucun
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 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 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.
Sans le tableau vu, un parcours tournerait en rond sur le moindre cycle.
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 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
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.
Avant l'appel
Si le cas de base n'est jamais atteint, la pile finit par déborder : Java lève une StackOverflowError.5
appels avant le débordement, sur l'ordinateur qui a servi à vérifier cette fiche.
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.
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).
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
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.
Un arbre, c'est un nœud et une liste de sous-arbres : les algorithmes récursifs s'y écrivent naturellement.
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).
tailleTotale(cours) commence : total = 2, puis la boucle appelle le premier enfant, maths.
tailleTotale(maths) : total = 10, puis appel sur exos. Trois cadres sur la pile : la hauteur plus un.
exos n'a pas d'enfant : la boucle ne fait rien, il renvoie 5. C'est le cas de base, implicite.
maths renvoie 10 + 5 = 15. Puis cours appelle info, une feuille, qui renvoie 3.
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.
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
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.
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.
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
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.
Sur le graphe de la fiche, il trouve 6 arêtes là où le BFS en trouve 2.
Deux petites routes peuvent être plus courtes qu'une longue route directe : il faut Dijkstra.
Avec if (n == 1) return 1;, fact(0) appelle fact(-1), puis fact(-2)… jusqu'au StackOverflowError. Écris n <= 1.
return n * fact(n) ne diminue jamais n : récursion infinie.
V² cases pour quelques arêtes par sommet : la liste d'adjacence est bien plus économe.
Cherche d'abord, puis ouvre le corrigé. Les réponses ont été vérifiées en exécutant le code Java de la fiche.
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.
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.
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.
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 ».
Douze questions pour finir
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.