Graphes

Contenus étudiés:

• Graphes : structures relationnelles.

• Sommets, arcs, arêtes, graphes orientés ou non orientés

• Algorithmes sur les graphes

Capacités attendues

• Modéliser des situations sous forme de graphes.

• Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs.

• Passer d’une représentation à une autre.

• Parcourir un graphe en profondeur d’abord, en largeur d’abord.

• Repérer la présence d’un cycle dans un graphe.

• Chercher un chemin dans un graphe.