Leçon 14 : Graphes — BFS et DFS

Pense à une carte de villes reliées par des routes, ou à des amis sur un réseau social. Tout ce qui est « des points et des relations entre eux » est un « graphe » : des nœuds reliés par des arêtes (edges). Deux façons de parcourir un graphe : BFS se propage cercle par cercle comme une onde dans l'e

BFS, c'est comme une onde dans l'eau : on part d'un point et on se propage cercle par cercle, le plus proche d'abord. DFS, c'est comme marcher dans un labyrinthe — on va jusqu'au bout d'un chemin, et si on est bloqué on recule et on essaie un autre.

parcours de graphe: Visiter systématiquement chaque nœud accessible depuis un nœud de départ, à l'aide de BFS (une file) ou de DFS (une pile/récursion).
dictionnaire d'adjacence: Une représentation de graphe où chaque nœud est associé à sa liste de voisins : {node: [neighbors]} — accès aux voisins en O(1).
ensemble visited: Un ensemble (set) qui marque les nœuds déjà parcourus, pour éviter de les revisiter et empêcher les boucles infinies.