Graphes

Graphes

Cette partie concentre à la fois la partie “structure de donnée graphe” et algorithmes sur les graphes.

Supports de cours #

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.