Graphes

Parcours BFS et DFS, tri topologique et plus court chemin (Dijkstra) : réseaux, grilles et dépendances.

1. 01

   Graphes : BFS et DFS

   Un graphe modélise des relations (réseau, carte, dépendances) : BFS trouve le plus court chemin non pondéré, DFS explore en profondeur.

2. 02

   Tri topologique : ordonner des dépendances

   Ordonner des tâches pour que chaque dépendance passe avant ce qui en dépend : c'est un graphe orienté acyclique.

3. 03

   Dijkstra : plus court chemin pondéré

   Avec des poids positifs sur les arêtes, on développe toujours le sommet le plus proche non encore finalisé, grâce à un heap.