Le parcours en largeur (BFS) explore un graphe niveau par niveau, en utilisant une file, et trouve le plus court chemin en nombre d'arêtes. Le parcours en profondeur (DFS) suit une branche jusqu'au bout avant de revenir, en utilisant une pile ou la récursion. Tous deux visitent chaque noeud en notant ceux déjà vus.
Exemple
from collections import deque
def bfs(g, s):
vus, f = {s}, deque([s])
while f:
n = f.popleft()
for v in g[n]:
if v not in vus:
vus.add(v); f.append(v)