Algorithmes sur les graphes

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.