Les graphes

Au programme de la partie « Structures de données »

Contenus	Capacités attendues	Commentaires
Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés.	- 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 à une autre.	On s’appuie sur des exemples comme le réseau routier, le réseau électrique, internet, les réseaux sociaux. - Le choix de la représentation dépend du traitement qu’on veut mettre en place : on fait le lien avec la rubrique « algorithmique ».

Contenus	Capacités attendues	Commentaires
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.	- Le parcours d’un labyrinthe et le routage dans internet sont des exemples d’algorithme sur les graphes. - L’exemple des graphes permet d’illustrer l’utilisation des classes en programmation.