Algorithmique · Écoles d'ingénieurs — ENSIAS

Graphes : Représentations 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ésentations :
- Matrice d'adjacence : Matrice $M$ de taille $n \times n$ où $M[i][j] = 1$ s'il existe une arête entre $i$ et $j$ , 0 sinon. Complexité spatiale $O(n^2)$ .
- Liste d'adjacence : Tableau de listes chaînées. Chaque case $i$ contient la liste des voisins de $i$ . Complexité spatiale $O(n + m)$ .
Parcours :
- BFS (Breadth-First Search) : Utilise une File (Queue). Explore les voisins de niveau 1, puis 2, etc.
- DFS (Depth-First Search) : Utilise une Pile (Stack) ou la récursivité. Explore le plus profondément possible avant de revenir en arrière.

Méthodes à maîtriser

Passer d'une matrice à une liste d'adjacence.
Tracer manuellement l'ordre de visite des sommets pour BFS et DFS.
Choisir la structure adaptée selon la densité du graphe (matrice pour graphe dense, liste pour graphe creux).

Exemples corrigés

BFS : Pour un graphe $A-B, A-C, B-D$ , en partant de A : on visite A, puis la file devient [B, C], on visite B, on ajoute D, file [C, D], on visite C, on visite D. Ordre : A, B, C, D.
DFS : En partant de A : on visite A, on va vers B, de B on va vers D, on revient à A, on va vers C. Ordre : A, B, D, C.

Erreurs fréquentes

Oublier de marquer les sommets comme "visités" (risque de boucle infinie).
Confondre l'ordre de visite avec l'ordre d'insertion dans la file/pile.
Ne pas gérer les graphes non connexes (oublier de lancer le parcours sur les sommets isolés).

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ésentations :
- Matrice d'adjacence : Matrice $M$ de taille $n \times n$ où $M[i][j] = 1$ s'il existe une arête entre $i$ et $j$, 0 sinon. Complexité spatiale $O(n^2)$.
- Liste d'adjacence : Tableau de listes chaînées. Chaque case $i$ contient la liste des voisins de $i$. Complexité spatiale $O(n + m)$.
Parcours :
- BFS (Breadth-First Search) : Utilise une File (Queue). Explore les voisins de niveau 1, puis 2, etc.
- DFS (Depth-First Search) : Utilise une Pile (Stack) ou la récursivité. Explore le plus profondément possible avant de revenir en arrière.

Méthodes à maîtriser

Passer d'une matrice à une liste d'adjacence.
Tracer manuellement l'ordre de visite des sommets pour BFS et DFS.
Choisir la structure adaptée selon la densité du graphe (matrice pour graphe dense, liste pour graphe creux).

Exemples corrigés

BFS : Pour un graphe $A-B, A-C, B-D$, en partant de A : on visite A, puis la file devient [B, C], on visite B, on ajoute D, file [C, D], on visite C, on visite D. Ordre : A, B, C, D.
DFS : En partant de A : on visite A, on va vers B, de B on va vers D, on revient à A, on va vers C. Ordre : A, B, D, C.

Erreurs fréquentes

Oublier de marquer les sommets comme "visités" (risque de boucle infinie).
Confondre l'ordre de visite avec l'ordre d'insertion dans la file/pile.
Ne pas gérer les graphes non connexes (oublier de lancer le parcours sur les sommets isolés).

🌉 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ésentations et parcours (BFS, DFS)

1/4

Quelle structure de données est utilisée pour implémenter le BFS ?

❓ Questions fréquentes

Est-ce que BFS visite tous les sommets ?

Si le graphe est connexe, oui. Si le graphe n'est pas connexe, BFS ne visitera que la composante connexe contenant le sommet de départ. Il faut lancer BFS sur chaque sommet non visité pour couvrir tout le graphe.

💡 À retenir : Toujours vérifier la connexité.

C'est quoi la différence entre BFS et DFS ?

BFS (Breadth-First Search) explore le graphe "couche par couche". Il visite tous les voisins directs avant de passer aux voisins des voisins.
DFS (Depth-First Search) explore le graphe "en profondeur". Il suit un chemin jusqu'à ce qu'il soit bloqué, puis revient en arrière (backtracking).

💡 À retenir : BFS = File (FIFO), DFS = Pile (LIFO) ou Récursivité.

Kifach n-3ref wach n-khdem b matrice aw liste d'adjacence ?

Si ton graphe est "dense" (beaucoup d'arêtes, proche de $n^2$ ), la matrice est plus simple à manipuler.
Si ton graphe est "creux" (peu d'arêtes), la liste d'adjacence est beaucoup plus efficace en mémoire ( $O(n+m)$ contre $O(n^2)$ ).

💡 À retenir : Liste d'adjacence = gain de mémoire pour les grands graphes.

Si ton graphe est "dense" (beaucoup d'arêtes, proche de $n^2$), la matrice est plus simple à manipuler.
Si ton graphe est "creux" (peu d'arêtes), la liste d'adjacence est beaucoup plus efficace en mémoire ($O(n+m)$ contre $O(n^2)$).

💡 À retenir : Liste d'adjacence = gain de mémoire pour les grands graphes.

Est-ce que le résultat d'un parcours DFS est unique ?

Non. L'ordre de visite dépend de l'ordre dans lequel tu explores les voisins d'un sommet. Si tu as deux voisins B et C, commencer par B ou par C donnera deux parcours différents.

💡 À retenir : L'ordre dépend du choix arbitraire des voisins.

chno hiya l'utilité dyal "visité" f l'algorithme ?

C'est indispensable pour éviter de tourner en rond (boucles infinies) dans un graphe qui contient des cycles. Sans ce tableau, l'algorithme repasserait indéfiniment sur les mêmes sommets.

💡 À retenir : Toujours marquer un sommet comme visité dès qu'on le traite.

Comment représenter un graphe orienté avec une matrice ?

Dans une matrice $M$ , si tu as une arête de $i$ vers $j$ , tu mets $M[i][j] = 1$ . Attention, contrairement au graphe non orienté, la matrice n'est pas forcément symétrique.

💡 À retenir : $M[i][j] \neq M[j][i]$ en général pour les graphes orientés.

Dans une matrice $M$, si tu as une arête de $i$ vers $j$, tu mets $M[i][j] = 1$. Attention, contrairement au graphe non orienté, la matrice n'est pas forcément symétrique.

💡 À retenir : $M[i][j] \neq M[j][i]$ en général pour les graphes orientés.

wach l'algorithme DFS kaykhdem ghir b récursivité ?

Non, tu peux utiliser une structure de données "Pile" (Stack) manuelle pour simuler la récursivité. C'est d'ailleurs souvent préférable pour éviter les erreurs de "Stack Overflow" sur de très grands graphes.

💡 À retenir : Pile ou Récursivité, c'est la même logique DFS.

kifach n-mthlo graphe f l'ordinateur ?

Tu as deux choix principaux :

Un tableau 2D (matrice) pour les graphes simples.
Un tableau de listes (ou vecteurs en C++) pour les graphes plus complexes ou creux.

💡 À retenir : Le choix dépend de la densité du graphe.

Est-ce que BFS peut trouver le chemin le plus court ?

Oui, dans un graphe non pondéré, le BFS garantit de trouver le chemin le plus court en nombre d'arêtes entre la source et n'importe quel sommet.

💡 À retenir : BFS est optimal pour le plus court chemin sans poids.

Est-ce qu'on peut utiliser BFS sur un graphe orienté ?

Absolument. Le principe reste le même : on explore les sommets accessibles via les arcs sortants.

💡 À retenir : L'orientation ne change que la direction des déplacements.

chnou l'avantage dyal liste d'adjacence f l'espace ?

Elle ne stocke que les arêtes existantes. Si tu as 1000 sommets mais seulement 2000 arêtes, la matrice prendrait $1000^2 = 1 000 000$ cases, alors que la liste ne prendrait que $O(1000 + 2000)$ éléments.

💡 À retenir : Économie massive de mémoire.

Est-ce que le DFS peut être utilisé pour détecter un cycle ?

Oui, si lors d'un parcours DFS, tu rencontres un sommet qui est déjà dans la "pile de récursion" (ou marqué comme "en cours de visite"), alors il y a un cycle.

💡 À retenir : DFS est très puissant pour la détection de cycles.

✍️ Exercices type examen national

Exercice 1

Soit un graphe non orienté $G$ avec les sommets $\{1, 2, 3, 4, 5\}$ et les arêtes $\{(1,2), (1,3), (2,4), (3,4), (4,5)\}$ .

Donner la matrice d'adjacence de $G$ .
Donner la liste d'adjacence de $G$ .
Donner l'ordre de visite d'un parcours BFS en partant du sommet 1.

Exercice 1

Soit un graphe non orienté $G$ avec les sommets ${1, 2, 3, 4, 5}$ et les arêtes ${(1,2), (1,3), (2,4), (3,4), (4,5)}$.

Donner la matrice d'adjacence de $G$.
Donner la liste d'adjacence de $G$.
Donner l'ordre de visite d'un parcours BFS en partant du sommet 1.

Voir la correction détaillée : inscription gratuite

Exercice 2

On considère un graphe orienté. Expliquer pourquoi la complexité temporelle du DFS est $O(V+E)$ où $V$ est le nombre de sommets et $E$ le nombre d'arêtes.

Exercice 2

On considère un graphe orienté. Expliquer pourquoi la complexité temporelle du DFS est $O(V+E)$ où $V$ est le nombre de sommets et $E$ le nombre d'arêtes.

Voir la correction détaillée : inscription gratuite

Exercice 3

Écrire en pseudo-code l'algorithme BFS pour un graphe représenté par une liste d'adjacence.

Voir la correction détaillée : inscription gratuite

Un prof de Algorithmique 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 Algorithmique

Introduction à l'algorithmique et complexité Structures de données linéaires : Listes, Piles et Files Récursivité et méthodes de conception d'algorithmes Algorithmes de tri et de recherche Arbres binaires et arbres de recherche Structures de données avancées : Tas (Heaps) et Files de priorité Tables de hachage (Hash Tables)Algorithmes sur les graphes : Plus courts chemins et arbres couvrants Programmation dynamique Algorithmes gloutons Introduction à la théorie de la complexité (P vs NP)