Terminale · Numérique et sciences informatiques

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.

Aperçu gratuit
Illustration de la fiche « Algorithmes sur les graphes »

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.

Première page de l’Essentiel : Algorithmes sur les graphes
Ketty