| Cours | Date | Sujet | Matériel supplémentaire |
| 1 |
|
Introduction
- premières définitions
- les graphes sont partout
- représentation des graphes
- parcours en profondeur recursif
|
- notes de cours
- un parcours récursif en profondeur animé (sous Acrobat Reader) du labyrinthe.
Les sommets déjà vus sont noirs ou bleus. Les sommets bleus représentent
des sommets i dont l'appel récursif VISITE(i) n'est pas encore terminé.
Pour les sommets noirs, la date de fin a été déjà choisie.
|
| 2 |
|
- définitions : arbres et forêts
- calcul du nombre de composantes connexes d'un graphe non-orienté
- déterminer si un graphe est bipartie, 2-colorabilité
- parcours en profondeur itératif, piles
- Parcours en largeur, files
|
|
| 3 |
|
- calcul des plus courts chemin d'un graphe par un parcours en largeur
- classification des arcs par un parcours en profondeur
- detection de cycle
- algorithmes de tri topologique
|
|
| 4 |
|
- fermeture transitive
- calcul de composantes fortement connexes (Kosaraju)
|
|
| 5 |
|
- algorithme de Warshall
- algorithme de Kosaraju
- algorithme de Tarjan
|
|
| 6 |
|
- graphes pondérés
- arbres couvrants minimaux (ACM)
- algorithme glouton abstrait pour les ACM
- algorithme de Prim
|
|
| 7 |
|
- arbres couvrants minimaux (ACM)
- algorithme de Kruskal
- Union-find
|
|
| 8 |
|
- plus courts chemins
- algorithme ordinal
- algorithme de Dijkstra
|
|
| 9 |
|
- compléments pour l'implémentation des algorithmes précédents avec des files de priorités
- algorithme de Bellman-Ford
|
|
| 10 |
|
- Problèmes d'ordonnancement
|
|
| 11 |
|
|
|