🎯 Objectifs de la lecon
- •Comprendre le principe du parcours en largeur (BFS) et du parcours en profondeur (DFS).
- •Savoir détecter un cycle dans un graphe non orienté avec DFS.
- •Savoir calculer le plus court chemin dans un graphe non pondéré avec BFS.
Les graphes sont des structures qui modélisent des relations entre objets. Dans ce chapitre, tu vas apprendre à les parcourir systématiquement, à détecter des cycles et à trouver le chemin le plus court entre deux sommets.
Représentation d'un graphe en Python
Un graphe est composé de sommets (ou nœuds) et d'arêtes qui relient deux sommets. En Python, on le représente souvent par une liste d'adjacence : un dictionnaire dont chaque clé est un sommet, et la valeur est la liste de ses voisins.
« graphe = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']} »
Point fort : Cette structure permet d'accéder rapidement aux voisins d'un sommet.
✔️ A retenir
Un graphe non orienté a des arêtes sans direction : si A est voisin de B, alors B est voisin de A. La liste d'adjacence le reflète.
Parcours en profondeur (DFS)
Le parcours en profondeur (DFS) explore un graphe en allant le plus loin possible avant de revenir en arrière. Il utilise une pile (LIFO) pour mémoriser les sommets à visiter.
On marque chaque sommet visité pour éviter les boucles. L'algorithme commence par un sommet de départ, le marque, puis empile ses voisins non visités. On dépile ensuite pour continuer.
« Avec le graphe précédent, un DFS depuis A visite A, puis B, puis D, puis C (ordre possible). »
Point fort : Le DFS explore en profondeur avant de revenir.
⚠️ Attention
Attention : si le graphe n'est pas connexe, certains sommets ne seront pas visités. Il faut alors relancer le parcours depuis un sommet non visité.
Parcours en largeur (BFS)
Le parcours en largeur (BFS) explore un graphe niveau par niveau. Il utilise une file (FIFO) pour mémoriser les sommets à visiter.
On commence par un sommet de départ, on le marque, puis on enfile ses voisins non visités. On défile ensuite le premier sommet de la file et on répète.
« Avec le même graphe, un BFS depuis A visite A, puis B et C (dans l'ordre), puis D. »
Point fort : Le BFS visite les sommets par distance croissante depuis le départ.
✔️ A retenir
DFS utilise une pile (empiler/dépiler). BFS utilise une file (enfiler/défiler).
Détection de cycles dans un graphe non orienté
Un cycle est une suite d'arêtes qui revient au sommet de départ sans passer deux fois par la même arête. Pour détecter un cycle, on utilise un DFS.
Pendant le DFS, on garde trace du parent de chaque sommet (le sommet depuis lequel on est arrivé). Si on rencontre un voisin déjà visité qui n'est pas le parent, alors il y a un cycle.
« Dans le graphe {'A':['B','C'], 'B':['A','C'], 'C':['A','B']}, le DFS depuis A voit B (parent A), puis depuis B voit C (déjà visité et non parent) : cycle détecté. »
Point fort : La condition 'voisin visité et non parent' est la clé de la détection.
⚠️ Attention
Cette méthode fonctionne pour les graphes non orientés. Pour les graphes orientés, la détection est différente (on utilise des couleurs).
Plus court chemin dans un graphe non pondéré avec BFS
Dans un graphe non pondéré (toutes les arêtes ont un coût de 1), le BFS donne le plus court chemin en nombre d'arêtes entre un sommet de départ et tous les autres.
On modifie le BFS : on stocke la distance (nombre d'arêtes) depuis le départ dans un dictionnaire. Au début, la distance du départ est 0. Quand on découvre un voisin non visité, sa distance est distance_actuelle + 1.
« Dans le graphe {'A':['B','C'], 'B':['D'], 'C':['D'], 'D':[]}, un BFS depuis A donne : distance A=0, B=1, C=1, D=2. »
Point fort : Le BFS garantit que la première fois qu'on atteint un sommet, c'est par le chemin le plus court.
✔️ A retenir
Pour obtenir le chemin lui-même, on stocke aussi le prédécesseur de chaque sommet (le sommet précédent sur le chemin). On remonte ensuite les prédécesseurs depuis la destination.
Erreurs fréquentes et mini-quiz
Erreur 1 : oublier de marquer un sommet comme visité avant de l'ajouter à la file/pile. Cela peut causer des visites infinies.
Erreur 2 : confondre file et pile. BFS utilise une file (FIFO), DFS une pile (LIFO).
Mini-quiz : 1) Quel parcours utilise une file ? 2) Dans un BFS, quelle est la distance du sommet de départ ? 3) Comment détecte-t-on un cycle dans un graphe non orienté ?
Corrections : 1) BFS. 2) 0. 3) Pendant un DFS, si on rencontre un voisin déjà visité qui n'est pas le parent, il y a un cycle.
