Fiches
Algorithmes sur les graphes
Savoir parcourir un graphe en profondeur d'abord et en largeur d'abord, repérer la présence d'un cycle et chercher un chemin entre deux sommets.
Consulter les définitions clés
Étudier un exemple guidé
Ce que dit la fiche
Les points essentiels
- Parcourir un graphe, c'est visiter ses sommets en suivant les arêtes, en marquant chaque sommet déjà visité pour ne jamais le traiter deux fois.
- Le parcours en profondeur d'abord descend le plus loin possible dans une branche avant de revenir en arrière ; il s'écrit avec une pile ou une fonction récursive.
- Le parcours en largeur d'abord visite tous les sommets proches du départ avant les sommets plus éloignés ; il s'écrit avec une file.
- Pour repérer un cycle, on signale un cycle dès qu'on rencontre un sommet déjà visité qui n'est pas le sommet d'où l'on vient.
- Pour chercher un chemin, on mémorise pour chaque sommet visité le sommet qui a permis de l'atteindre, puis on remonte cette chaîne depuis l'arrivée.
Les mots à connaître
- Graphe
- Ensemble de sommets reliés entre eux par des arêtes (graphe non orienté) ou par des arcs (graphe orienté).
- Sommet
- Élément de base d'un graphe ; on l'appelle aussi nœud.
- Arête
- Lien entre deux sommets d'un graphe non orienté ; on peut la parcourir dans les deux sens.
- Voisin
- Deux sommets sont voisins lorsqu'une arête les relie directement.
- Parcours en profondeur d'abord
- Parcours qui explore une branche jusqu'au bout avant de revenir en arrière pour explorer les autres branches.
- Parcours en largeur d'abord
- Parcours qui visite tous les voisins d'un sommet avant de passer aux sommets plus éloignés du départ.
- Cycle
- Chemin qui part d'un sommet et revient à ce même sommet.
- Chemin
- Suite de sommets voisins deux à deux, du sommet de départ au sommet d'arrivée.
La méthode, étape par étape
- Représenter le graphe par des listes d'adjacence : pour chaque sommet, la liste de ses voisins.
- Créer une structure des sommets visités, par exemple un ensemble, et y placer le sommet de départ.
- Parcours en largeur : mettre le départ dans une file ; retirer le premier sommet, marquer et enfiler ses voisins non visités ; répéter jusqu'à ce que la file soit vide.
- Parcours en profondeur : utiliser une pile ou une fonction récursive ; marquer le sommet, puis relancer le parcours sur chaque voisin non visité.
- Chercher un chemin : noter pour chaque sommet visité le sommet précédent ; à la fin, remonter la chaîne depuis l'arrivée jusqu'au départ.
- Repérer un cycle : signaler un cycle dès qu'un voisin déjà visité n'est pas le sommet d'où l'on vient.
Des exemples résolus
Graphe non orienté d'arêtes A-B, A-C, B-D, C-D, D-E. Les voisins sont listés par ordre alphabétique. Donne l'ordre de visite du parcours en largeur d'abord depuis A.
Correction
File de départ : [A], visités : {A}. Retirer A : ses voisins B et C ne sont pas visités. Ordre : A, B, C. File : [B, C]. Retirer B : son voisin A est déjà visité, son voisin D ne l'est pas. Ordre : A, B, C, D. File : [C, D]. Retirer C : ses voisins A et D sont déjà visités. Retirer D : ses voisins B et C sont déjà visités, son voisin E ne l'est pas. Ordre : A, B, C, D, E. File : [E]. Retirer E : son voisin D est déjà visité. Ordre final : A, B, C, D, E.
Avec le même graphe (A-B, A-C, B-D, C-D, D-E), donne l'ordre de visite du parcours en profondeur d'abord depuis A, puis propose un chemin de A vers E.
Correction
On visite A. Les voisins de A sont B puis C. On part sur B et on visite B. Les voisins de B sont A (déjà visité) puis D. On visite D. Les voisins de D sont B (déjà visité) puis C. On visite C. Les voisins de C sont A et D, tous deux déjà visités : on revient en arrière jusqu'à D. D a encore un voisin non visité, E : on visite E. Les voisins de E se réduisent à D, déjà visité : on revient en arrière. Ordre final : A, B, D, C, E. Chemin de A vers E : en partant de A, on va en B, puis en D, puis en E, ce qui donne le chemin A-B-D-E.
Les pièges à éviter
- Oublier de marquer les sommets visités : le parcours repasse sans cesse par les mêmes sommets et ne s'arrête plus.
- Utiliser une pile pour un parcours en largeur, ou une file pour un parcours en profondeur : l'ordre de visite change complètement.
- Croire qu'on a trouvé un cycle dès qu'on revoit le sommet d'où l'on vient : dans un graphe non orienté, il faut ignorer ce sommet précédent.
Teste-toi
Dans un parcours en largeur d'abord, quelle structure de données sert à mémoriser les sommets à traiter ?
Voir la réponse
Une file.
La file range les sommets dans leur ordre d'arrivée et les fait sortir dans ce même ordre. Le parcours en largeur traite ainsi les sommets du plus proche au plus éloigné du départ.
Graphe non orienté d'arêtes A-B, A-C, B-D, C-D, D-E. Quel est l'ordre de visite du parcours en largeur d'abord depuis A ?
Voir la réponse
A, B, C, D, E.
On part de A et on enfile ses voisins B et C. On traite ensuite B, qui fait entrer D, puis C, dont les voisins sont déjà visités. On traite D, qui fait entrer E, puis E. L'ordre de sortie de la file donne A, B, C, D, E.
Ce même graphe contient-il un cycle ? Si oui, donne-en un.
Voir la réponse
Oui, par exemple A-B-D-C-A.
On part de A, on suit l'arête vers B, puis vers D, puis vers C, et l'arête C-A ramène au départ. On obtient un chemin fermé, donc un cycle.
Ce que tu vas découvrir
- Parcourir un graphe, c'est visiter ses sommets en suivant les arêtes, en marquant chaque sommet déjà visité pour ne jamais le traiter deux fois.
- Le parcours en profondeur d'abord descend le plus loin possible dans une branche avant de revenir en arrière ; il s'écrit avec une pile ou une fonction récursive.
- Le parcours en largeur d'abord visite tous les sommets proches du départ avant les sommets plus éloignés ; il s'écrit avec une file.
- Pour repérer un cycle, on signale un cycle dès qu'on rencontre un sommet déjà visité qui n'est pas le sommet d'où l'on vient.
Dans cette expérience
- Lire les points essentiels
- Consulter les définitions clés
- Étudier un exemple guidé
Pour quel niveau ?
- Terminale
- Numérique et sciences informatiques
Cette fiche fait partie de notre collection MathématiquesDécouvre toutes nos fiches de 3e pour réviser efficacement !
Voir toutes les fiches de 3e