Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Parcours en largeur et en profondeur, plus courts chemins, arbres couvrants, coloration : les algorithmes de graphes du programme MPI.
Choisir sa représentation avant d'écrire une ligne
Un graphe se représente par une matrice d'adjacence ou par des listes d'adjacence, et ce choix conditionne toute la suite. La matrice teste l'existence d'une arête en temps constant mais occupe n² cases ; les listes énumèrent les voisins efficacement mais rendent le test d'adjacence plus coûteux. Sur les graphes creux — le cas courant en pratique — les listes gagnent. La première question d'un sujet porte souvent là-dessus.
Les algorithmes à maîtriser
Parcours : en largeur avec une file, en profondeur avec une pile ou par récursion. Ce sont les mêmes vingt lignes, à la structure de données près — et c'est exactement ce qu'il faut avoir compris. Plus courts chemins : Dijkstra avec un tas, Bellman-Ford quand les poids peuvent être négatifs, Floyd-Warshall pour toutes les paires. Arbres couvrants : Prim et Kruskal, avec l'union-find. Puis les classiques : composantes connexes, détection de cycle, tri topologique, bipartisme, coloration gloutonne.
Le parcours en largeur donne le plus court chemin — mais seulement sans poids
C'est l'erreur la plus fréquente. Un BFS trouve le chemin le plus court en nombre d'arêtes. Dès que les arêtes portent des poids différents, il faut Dijkstra. Réciproquement, sortir Dijkstra sur un labyrinthe où tous les déplacements coûtent 1, c'est perdre du temps pour rien.
Marquer à l'enfilement, pas au défilement
Dans un BFS, un sommet doit être marqué visité au moment où on l'ajoute à la file, pas quand on l'en retire. Sinon il y entre plusieurs fois et la complexité s'effondre — sur un graphe dense, le programme ne rend pas. C'est une ligne, et elle départage les copies.
Les exercices
Graphes 19 exercices
- BFS et DFS Parcours de graphes
- Algorithme de Dijkstra Plus court chemin pondéré
- Composantes Connexes BFS/DFS pour trouver toutes les composantes
- Détection de Cycle dans un Graphe Non Orienté DFS avec parent pour détecter les arêtes arrière
- Tri Topologique DAG — ordre d'exécution des tâches
- Algorithme de Bellman-Ford Plus courts chemins avec poids négatifs
- Algorithme de Prim Arbre couvrant minimal
- Algorithme de Kruskal Arbre couvrant minimal avec Union-Find
- Coloration de Graphe Algorithme glouton de coloration
- Plus Court Chemin dans un Labyrinthe BFS sur grille 2D
- Représentations d'un Graphe Matrice et liste d'adjacence
- Test de Bipartisme BFS et 2-coloration
- Détection de Cycle (graphe orienté) DFS avec coloriage à 3 couleurs
- Diamètre d'un Arbre Deux BFS successifs — une astuce élégante
- Algorithme de Floyd-Warshall Plus courts chemins entre toutes les paires
- Composantes Fortement Connexes (Kosaraju) Deux DFS sur le graphe et son transposé
- Algorithme A* sur Grille Recherche guidée par une heuristique
- Flot Maximal — Edmonds-Karp BFS dans le graphe résiduel
- Critère de Delaunay (in-circle) Test géométrique pour triangulation
Autres rubriques
- Exercices Python pour la prépa — CPGE scientifique et ECG
- Exercices SQL pour la prépa — bases de données en CPGE
- Exercices d'algorithmique en Python — tris, dichotomie, récursivité
- Exercices d'analyse numérique en Python — dichotomie, Newton, intégration
- Exercices Python pour la prépa ECG — probabilités, matrices, suites
- Exercices d'IA et d'apprentissage automatique en Python — CPGE
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.