BFS et DFS
Parcours de graphes
Enonce
G = {0:[1,2], 1:[0,3,4], 2:[0,4], 3:[1], 4:[1,2]}
- bfs(G, source) — ordre BFS
- dfs(G, source) — ordre DFS itératif
- distance(G, s, t) — nb d'arêtes du plus court chemin
Signature attendue
def bfs(G: dict, source: int) -> list:
def dfs(G: dict, source: int) -> list:
def distance(G: dict, s: int, t: int) -> int:Exemple
bfs({0:[1,2], 1:[0,3,4], 2:[0,4], 3:[1], 4:[1,2]}, 0)→[0, 1, 2, 3, 4]
📖 Rappel de cours
BFS — file FIFO :
Niveaux croissants. Plus courts chemins. $O(|V|+|E|)$.
DFS — pile LIFO :
Profondeur. Détecte cycles. $O(|V|+|E|)$.
⚠ Le piège : Ce sont les mêmes vingt lignes, à la structure de données près : une file donne le parcours en largeur, une pile celui en profondeur. Marquer un sommet à l'enfilement, jamais au défilement, sinon il y entre plusieurs fois. Et le BFS ne donne le plus court chemin que si les arêtes sont sans poids.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.