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.

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.
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.
Un exemple pour comprendre
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.
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.

