Informatique · Classes prépa (CPGE) — 2ème année — TSI

Graphes : Représentation et parcours (BFS, DFS)

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

Un graphe $G = (V, E)$ est défini par un ensemble de sommets $V$ et un ensemble d'arêtes $E$ .

Représentation :
- Matrice d'adjacence $M$ : $M[i][j] = 1$ s'il existe une arête entre $i$ et $j$ , 0 sinon. Complexité spatiale $O(|V|^2)$ .
- Liste d'adjacence : Dictionnaire ou liste de listes où chaque sommet pointe vers ses voisins. Complexité spatiale $O(|V| + |E|)$ .
Parcours :
- BFS (Breadth-First Search) : Utilise une file (FIFO). Idéal pour trouver le plus court chemin dans un graphe non pondéré.
- DFS (Depth-First Search) : Utilise une pile (LIFO) ou la récursion. Idéal pour détecter des cycles ou explorer toutes les composantes.

Méthodes à maîtriser

Passer de la représentation matricielle à la liste d'adjacence et inversement.
Écrire l'algorithme BFS avec une file collections.deque.
Écrire l'algorithme DFS de manière récursive.
Calculer la complexité temporelle : $O(|V| + |E|)$ pour les deux parcours.

Exemples corrigés

BFS : Pour un graphe donné, marquer le sommet de départ comme visité, l'enfiler. Tant que la file n'est pas vide, défiler, traiter, et enfiler les voisins non visités.
DFS : Pour un sommet $u$ , marquer $u$ comme visité, puis pour chaque voisin $v$ non visité, appeler récursivement DFS(v).

Erreurs fréquentes

Oublier de marquer un sommet comme "visité", ce qui provoque une boucle infinie.
Confondre la complexité de la matrice ( $O(|V|^2)$ ) avec celle de la liste d'adjacence ( $O(|V|+|E|)$ ).
Utiliser une liste simple au lieu d'une deque pour le BFS (perte de performance en $O(n)$ pour pop(0)).

L'essentiel du cours

Un graphe $G = (V, E)$ est défini par un ensemble de sommets $V$ et un ensemble d'arêtes $E$.

Représentation :
- Matrice d'adjacence $M$ : $M[i][j] = 1$ s'il existe une arête entre $i$ et $j$, 0 sinon. Complexité spatiale $O(|V|^2)$.
- Liste d'adjacence : Dictionnaire ou liste de listes où chaque sommet pointe vers ses voisins. Complexité spatiale $O(|V| + |E|)$.
Parcours :
- BFS (Breadth-First Search) : Utilise une file (FIFO). Idéal pour trouver le plus court chemin dans un graphe non pondéré.
- DFS (Depth-First Search) : Utilise une pile (LIFO) ou la récursion. Idéal pour détecter des cycles ou explorer toutes les composantes.

Méthodes à maîtriser

Passer de la représentation matricielle à la liste d'adjacence et inversement.
Écrire l'algorithme BFS avec une file collections.deque.
Écrire l'algorithme DFS de manière récursive.
Calculer la complexité temporelle : $O(|V| + |E|)$ pour les deux parcours.

Exemples corrigés

BFS : Pour un graphe donné, marquer le sommet de départ comme visité, l'enfiler. Tant que la file n'est pas vide, défiler, traiter, et enfiler les voisins non visités.
DFS : Pour un sommet $u$, marquer $u$ comme visité, puis pour chaque voisin $v$ non visité, appeler récursivement DFS(v).

Erreurs fréquentes

Oublier de marquer un sommet comme "visité", ce qui provoque une boucle infinie.
Confondre la complexité de la matrice ($O(|V|^2)$) avec celle de la liste d'adjacence ($O(|V|+|E|)$).
Utiliser une liste simple au lieu d'une deque pour le BFS (perte de performance en $O(n)$ pour pop(0)).

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Graphes : Représentation et parcours (BFS, DFS)

1/4

Quelle est la complexité spatiale d'une matrice d'adjacence pour un graphe de $N$ sommets ?

❓ Questions fréquentes

C'est quoi la différence entre BFS et DFS au niveau de la mémoire ?

BFS utilise une file (queue) : il stocke tous les voisins d'un niveau avant de passer au suivant.
DFS utilise une pile (stack) ou la pile d'appels récursifs : il stocke le chemin en cours.
En cas de graphe très large, BFS peut saturer la mémoire car il garde beaucoup de sommets en attente.

💡 À retenir : BFS est "large" (consomme plus de mémoire en largeur), DFS est "profond" (consomme selon la profondeur du graphe).

Kifach n7seb la complexité d'un parcours BFS ?

Chaque sommet est ajouté dans la file une seule fois : $O(|V|)$ .
Chaque arête est parcourue pour vérifier les voisins : $O(|E|)$ .
La complexité totale est donc la somme des deux.

💡 À retenir : La complexité temporelle est toujours $O(|V| + |E|)$ .

Chaque sommet est ajouté dans la file une seule fois : $O(|V|)$.
Chaque arête est parcourue pour vérifier les voisins : $O(|E|)$.
La complexité totale est donc la somme des deux.

💡 À retenir : La complexité temporelle est toujours $O(|V| + |E|)$.

Est-ce qu'on peut utiliser DFS pour trouver le plus court chemin ?

Non, DFS explore un chemin jusqu'au bout avant de revenir en arrière.
Il peut trouver un chemin, mais pas forcément le plus court.
BFS est l'algorithme standard pour le plus court chemin dans un graphe non pondéré.

💡 À retenir : BFS = plus court chemin, DFS = exploration/cycle.

Chno hiya la différence bin graphe orienté et non orienté f la matrice ?

Graphe non orienté : La matrice est symétrique par rapport à la diagonale ( $M[i][j] = M[j][i]$ ).
Graphe orienté : La matrice n'est pas forcément symétrique, car l'arête va de $i$ vers $j$ mais pas forcément de $j$ vers $i$ .

💡 À retenir : Symétrie = non orienté.

Graphe non orienté : La matrice est symétrique par rapport à la diagonale ($M[i][j] = M[j][i]$).
Graphe orienté : La matrice n'est pas forcément symétrique, car l'arête va de $i$ vers $j$ mais pas forcément de $j$ vers $i$.

💡 À retenir : Symétrie = non orienté.

Comment savoir si un graphe est connexe avec un parcours ?

Lancer un BFS ou DFS à partir d'un sommet quelconque.
Compter le nombre de sommets visités.
Si le nombre de sommets visités est égal au nombre total de sommets du graphe, alors il est connexe.

💡 À retenir : Connexité = tous les sommets sont accessibles.

Wach DFS récursif hsan mn DFS itératif ?

Récursif : Plus simple à écrire et à lire.
Itératif : Plus robuste pour les très grands graphes (évite l'erreur RecursionError).
Les deux ont la même complexité.

💡 À retenir : Utilise la récursion pour le confort, l'itératif pour la sécurité mémoire.

Pourquoi on utilise une deque au lieu d'une list pour le BFS ?

list.pop(0) en Python prend un temps $O(n)$ car il faut décaler tous les éléments.
collections.deque.popleft() prend un temps $O(1)$ .
Cela change la complexité globale du BFS de $O(|V|^2)$ à $O(|V| + |E|)$ .

💡 À retenir : Toujours utiliser deque pour les files.

list.pop(0) en Python prend un temps $O(n)$ car il faut décaler tous les éléments.
collections.deque.popleft() prend un temps $O(1)$.
Cela change la complexité globale du BFS de $O(|V|^2)$ à $O(|V| + |E|)$.

💡 À retenir : Toujours utiliser deque pour les files.

Est-ce qu'un graphe peut avoir plusieurs composantes connexes ?

Oui, c'est un graphe non connexe.
On peut le détecter en lançant un parcours sur chaque sommet non encore visité.
Chaque lancement de parcours correspond à une composante connexe.

💡 À retenir : Plusieurs composantes = plusieurs parcours nécessaires.

Kifach n'représentiw un graphe avec des poids sur les arêtes ?

Matrice d'adjacence : On remplace 1 par le poids $w$ et 0 par l'infini ( $\infty$ ).
Liste d'adjacence : On stocke des tuples (voisin, poids) au lieu de juste le voisin.

💡 À retenir : La structure change pour inclure la valeur du poids.

Matrice d'adjacence : On remplace 1 par le poids $w$ et 0 par l'infini ($\infty$).
Liste d'adjacence : On stocke des tuples (voisin, poids) au lieu de juste le voisin.

💡 À retenir : La structure change pour inclure la valeur du poids.

Est-ce que le DFS peut boucler à l'infini ?

Oui, s'il y a un cycle et qu'on ne garde pas de trace des sommets visités.
Il faut toujours utiliser un ensemble visites pour marquer les sommets déjà traités.

💡 À retenir : visites est obligatoire pour éviter les cycles.

C'est quoi un graphe complet ?

C'est un graphe où chaque sommet est relié à tous les autres sommets.
Il possède $|V| \times (|V|-1) / 2$ arêtes.

💡 À retenir : Complet = tout le monde est lié à tout le monde.

C'est un graphe où chaque sommet est relié à tous les autres sommets.
Il possède $|V| \times (|V|-1) / 2$ arêtes.

💡 À retenir : Complet = tout le monde est lié à tout le monde.

Est-ce que le programme demande de savoir Dijkstra ?

(à vérifier par le professeur) : Le programme 2025-2026 se concentre sur BFS/DFS. Dijkstra est généralement hors programme pour cette section spécifique.

💡 À retenir : Concentre-toi sur BFS et DFS.

✍️ Exercices type examen national

Exercice 1

Soit un graphe $G$ défini par ses sommets $V = \{A, B, C, D, E\}$ et ses arêtes $E = \{(A,B), (A,C), (B,D), (C,D), (D,E)\}$ .

Donner la matrice d'adjacence de ce graphe (supposé non orienté).
Donner la liste d'adjacence.
Effectuer un parcours BFS en partant de A. Donner l'ordre de visite.

Exercice 1

Soit un graphe $G$ défini par ses sommets $V = {A, B, C, D, E}$ et ses arêtes $E = {(A,B), (A,C), (B,D), (C,D), (D,E)}$.

Donner la matrice d'adjacence de ce graphe (supposé non orienté).
Donner la liste d'adjacence.
Effectuer un parcours BFS en partant de A. Donner l'ordre de visite.

Voir la correction détaillée : inscription gratuite

Exercice 2

Écrire une fonction Python est_connexe(graphe) qui prend en entrée un dictionnaire représentant une liste d'adjacence et retourne True si le graphe est connexe, False sinon.

Voir la correction détaillée : inscription gratuite

Exercice 3

Soit un graphe orienté. Expliquer pourquoi le DFS est plus adapté que le BFS pour détecter un cycle.

Voir la correction détaillée : inscription gratuite

Un prof de Informatique pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Informatique

Révision et approfondissement du langage Python Complexité des algorithmes Structures de données : Listes, Piles et Files Structures de données : Arbres binaires et Arbres binaires de recherche Algorithmes de tri et de recherche Programmation dynamique Bases de données relationnelles et langage SQL Architecture des ordinateurs et systèmes d'exploitation