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.

TerminaleNumérique et sciences informatiques

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.

Cette fiche fait partie de notre collection MathématiquesDécouvre toutes nos fiches de 3e pour réviser efficacement !