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 à 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 ». |
Au programme de la partie « 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. |
Documents
- Doc. Parcours de graphes