Cette partie concentre à la fois la partie “structure de donnée graphe” et algorithmes sur les graphes.
Supports de cours #
- cours : introduction
- cours : La structure de données graphe
- TD : les bases
- TD : autres exercices basiques
- TD : deux cas d’étude
- TD : parcourir arbres et graphes
- cours : algorithmes sur les graphes
- resumé
Dans cette partie, il y a aussi un TP “classique” et deux TP sur colab.
Programme structure de données #
Contenus : Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés.
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.
Commentaires : 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 ».
Programme algorithmique #
Contenus : Algorithmes sur les graphes.
Capacités attendues : 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.
Commentaires : 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.