C12 : Compétences

Notions de graphes

Modéliser des situations sous forme de graphes.

Sommets, arcs, arêtes

Graphes orientés ou non orientés.

Implémentation des 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.

Algorithmes sur les graphes

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.