BFS : plus court chemin et parcours par niveaux
Utilisez BFS pour trouver le plus court chemin dans un graphe non pondéré, résolvez word-ladder niveau par niveau et clonez un graphe avec une table de hachage.
BFS : plus court chemin et parcours par niveaux est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
BFS et plus court chemin dans les graphes non pondérés
BFS trouve le plus court chemin (avec le moins d’arêtes) dans un graphe non pondéré, car il explore les nœuds par ordre de distance croissante depuis la source. La première fois qu’un nœud est atteint pendant BFS, il l’est par un chemin aussi court que possible. Cette propriété ne s’applique pas à DFS. Pour les graphes pondérés dont les poids sont non négatifs, utilisez plutôt l’algorithme de Dijkstra : BFS considère implicitement que toutes les arêtes ont un poids de 1.
from collections import deque, defaultdict
def shortest_path(graph, start, end):
if start == end:
return 0
visited = {start}
queue = deque([(start, 0)]) # (node, distance)
while queue:
node, dist = queue.popleft()
for neighbour in graph[node]:
if neighbour == end:
return dist + 1
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, dist + 1))
return -1 # no path found
graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(0,3),(1,4)]:
graph[u].append(v); graph[v].append(u)
print(shortest_path(graph, 0, 3)) # 1 (direct edge)
print(shortest_path(graph, 0, 4)) # 2 (0->1->4)Suivi du véritable plus court chemin
Pour reconstruire le chemin réel (et pas seulement sa longueur), maintenez un dictionnaire des parents qui indique comment chaque nœud a été atteint. Lorsque vous atteignez la destination, remontez la carte des parents de la fin vers le début, puis inversez le résultat. Cela ajoute un espace O(V) pour la carte des parents, mais fournit le chemin complet en O(longueur du chemin) après la fin de BFS.
from collections import deque, defaultdict
def shortest_path_with_route(graph, start, end):
parent = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
if node == end:
break
for nb in graph[node]:
if nb not in parent:
parent[nb] = node
queue.append(nb)
if end not in parent:
return [] # no path
# Reconstruct path by tracing back
path = []
node = end
while node is not None:
path.append(node)
node = parent[node]
return path[::-1] # reverse
graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(0,4),(4,3)]:
graph[u].append(v); graph[v].append(u)
print(shortest_path_with_route(graph, 0, 3)) # [0, 4, 3] or [0, 1, 2, 3]Échelle de mots : BFS sur un graphe implicite
Échelle de mots (LeetCode #127) demande de trouver le nombre minimal de modifications d’un seul caractère pour transformer un mot de départ en un mot d’arrivée, chaque mot intermédiaire devant figurer dans un dictionnaire. Il s’agit d’un BFS sur un graphe implicite dans lequel les nœuds sont des mots et les arêtes relient les mots qui diffèrent d’une lettre. Générez toutes les mutations d’une lettre et vérifiez qu’elles appartiennent à l’ensemble de mots. BFS garantit la séquence de transformations minimale.
from collections import deque
def word_ladder(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)])
visited = {begin_word}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == end_word:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(word_ladder('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5Parcours par niveaux : suivi de la distance
Le parcours par niveaux regroupe les nœuds selon leur distance à la source, ce qui est directement utile pour les problèmes nécessitant un traitement niveau par niveau. Suivez la distance en la stockant dans l’élément de la file sous forme de tuple (node, dist), ou utilisez la technique fondée sur la taille de la file (notez la taille de la file avant chaque niveau, traitez exactement ce nombre de nœuds, puis incrémentez un compteur de niveaux). Les deux approches donnent des résultats identiques.
from collections import deque, defaultdict
def bfs_levels(graph, start):
levels = {}
visited = {start}
queue = deque([start])
dist = 0
while queue:
# Process all nodes at current distance
for _ in range(len(queue)):
node = queue.popleft()
levels[node] = dist
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
dist += 1
return levels
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,3),(2,3),(3,4)]:
graph[u].append(v); graph[v].append(u)
print(bfs_levels(graph, 0)) # {0:0, 1:1, 2:1, 3:2, 4:3}Clonage d’un graphe
Clonage d’un graphe (LeetCode #133) crée une copie complète d’un graphe non orienté connexe. Utilisez BFS et une table de hachage associant les nœuds d’origine à leurs clones. Lors de la première visite d’un nœud, créez son clone et ajoutez-le à la table. Lors du traitement des voisins, recherchez leurs clones dans la table ou créez-les, puis reliez les arêtes. La table de hachage joue un double rôle : elle suit les nœuds visités et associe les originaux à leurs copies.
from collections import deque
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def clone_graph(node):
if not node:
return None
old_to_new = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for nb in curr.neighbors:
if nb not in old_to_new:
old_to_new[nb] = Node(nb.val)
queue.append(nb)
old_to_new[curr].neighbors.append(old_to_new[nb])
return old_to_new[node]
# Build a simple graph: 1 -- 2 -- 3 -- 4 -- 1
n1 = Node(1); n2 = Node(2); n3 = Node(3); n4 = Node(4)
n1.neighbors = [n2, n4]; n2.neighbors = [n1, n3]
n3.neighbors = [n2, n4]; n4.neighbors = [n3, n1]
cloned = clone_graph(n1)
print(cloned.val, [n.val for n in cloned.neighbors]) # 1 [2, 4]BFS bidirectionnel
Le BFS bidirectionnel démarre simultanément depuis la source et la destination, en développant un niveau à la fois depuis chaque extrémité. Lorsque les deux frontières se rencontrent, vous avez trouvé le plus court chemin. Pour les grands graphes, cela réduit l’espace de recherche de O(b^d) à O(2 * b^(d/2)), où b est le facteur de branchement et d la longueur du chemin — une amélioration considérable pour les graphes très connectés, comme les échelles de mots avec de grands dictionnaires.
from collections import defaultdict
def word_ladder_bidir(begin, end, word_list):
word_set = set(word_list)
if end not in word_set:
return 0
front, back = {begin}, {end}
visited = {begin, end}
steps = 1
while front and back:
# Always expand the smaller frontier
if len(front) > len(back):
front, back = back, front
next_front = set()
for word in front:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nw = word[:i] + c + word[i+1:]
if nw in back: # frontiers met!
return steps + 1
if nw in word_set and nw not in visited:
visited.add(nw)
next_front.add(nw)
front = next_front
steps += 1
return 0
print(word_ladder_bidir('hit','cog',['hot','dot','dog','lot','log','cog'])) # 5BFS 0-1 pour les graphes pondérés
BFS 0-1 traite les graphes dont les poids d’arêtes sont uniquement 0 ou 1. Au lieu d’utiliser une file ordinaire, utilisez une file à double extrémité : utilisez append à l’arrière avec les arêtes de poids 1 (niveau suivant) et appendleft à l’avant avec les arêtes de poids 0 (même niveau). Vous obtenez ainsi un calcul des plus courts chemins en O(V + E), plus rapide que le O((V+E) log V) de Dijkstra lorsque les poids sont binaires. Cette méthode est courante dans les problèmes de grille où certains déplacements sont gratuits et d’autres coûtent 1.
from collections import deque
def zero_one_bfs(graph, start, n):
# graph: list of (neighbour, weight) where weight is 0 or 1
dist = [float('inf')] * n
dist[start] = 0
dq = deque([start])
while dq:
node = dq.popleft()
for nb, w in graph[node]:
if dist[node] + w < dist[nb]:
dist[nb] = dist[node] + w
if w == 0:
dq.appendleft(nb) # same level
else:
dq.append(nb) # next level
return dist
# Simple test:
graph = [[(1, 0), (2, 1)], # node 0: free to 1, cost 1 to 2
[(3, 1)], # node 1: cost 1 to 3
[(3, 0)], # node 2: free to 3
[]]
print(zero_one_bfs(graph, 0, 4)) # [0, 0, 1, 1]Murs et portes (BFS multisource)
Murs et portes remplit chaque pièce vide avec la distance jusqu’à la porte la plus proche. Utilisez un BFS multisource : initialisez simultanément la file avec toutes les portes (valeur 0), puis développez la recherche vers l’extérieur. La valeur de chaque cellule est définie par le niveau auquel elle est atteinte pour la première fois. Cette solution en O(mn) est plus efficace que l’exécution séparée d’un BFS depuis chaque pièce vide, qui nécessiterait O(m²n²).
from collections import deque
def walls_and_gates(rooms):
if not rooms:
return
rows, cols = len(rooms), len(rooms[0])
INF = float('inf')
queue = deque()
# Multi-source: all gates at distance 0
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0: # gate
queue.append((r, c))
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and rooms[nr][nc]==INF:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
rooms = [[float('inf'),-1,0,float('inf')],
[float('inf'),float('inf'),float('inf'),-1],
[float('inf'),-1,float('inf'),-1],
[0,-1,float('inf'),float('inf')]]
walls_and_gates(rooms)
print(rooms[0][0], rooms[1][1]) # 3, 2BFS pour Serpents et échelles
Serpents et échelles (LeetCode #909) est un problème de plus court chemin avec BFS sur une grille numérotée. Modélisez le plateau comme un graphe non pondéré dans lequel vous pouvez lancer le dé et avancer de 1 à 6 cases depuis n’importe quelle case, avec la possibilité d’arriver sur un serpent ou une échelle qui vous téléporte. BFS trouve le nombre minimal de lancers de dé. La principale difficulté consiste à convertir une position 1D en coordonnées 2D du plateau, en tenant compte de la disposition en boustrophédon (sens alterné des lignes).
from collections import deque
def snakes_and_ladders(board):
n = len(board)
def get_board(pos):
r, c = divmod(pos - 1, n)
if r % 2 == 1: c = n - 1 - c # alternating direction
return board[n - 1 - r][c]
visited = {1}
queue = deque([(1, 0)])
while queue:
pos, moves = queue.popleft()
for dice in range(1, 7):
next_pos = pos + dice
if next_pos > n * n:
break
val = get_board(next_pos)
if val != -1:
next_pos = val # snake or ladder
if next_pos == n * n:
return moves + 1
if next_pos not in visited:
visited.add(next_pos)
queue.append((next_pos, moves + 1))
return -1
print('BFS models game as an unweighted shortest-path problem')Complexité et optimisations de BFS
La complexité temporelle de BFS est O(V + E), car chaque sommet est ajouté à la file une fois et chaque arête est examinée un nombre constant de fois. La complexité spatiale est O(V) pour l’ensemble des nœuds visités et la file. Pour les graphes en grille, V = m*n et E = 4*m*n (chaque cellule possède 4 voisins), donc BFS sur une grille s’exécute en O(mn). Optimisation essentielle : utilisez un ensemble pour les éléments visités (recherche en O(1)), et non une liste (recherche en O(n)). Marquez les éléments comme visités lors de leur ajout à la file, et non lors de leur retrait.
# BFS on a graph with V vertices and E edges:
# Time: O(V + E) -- each vertex and edge visited once
# Space: O(V) -- visited set + queue
# BFS on an m x n grid:
# V = m*n cells
# E <= 4*m*n edges (4 directions, max)
# Time: O(m*n)
# Space: O(m*n)
# Common pitfalls:
# 1. Marking visited on dequeue (not enqueue) -> same node queued multiple times
# 2. Using a list for visited -> O(n) membership check -> O(V*E) total
# 3. Not handling disconnected graph -> BFS from single source misses components
print('O(V+E) time, O(V) space -- mark visited on enqueue')Zéro le plus proche dans une matrice binaire
Matrice 01 (LeetCode #542) trouve la distance entre chaque cellule et le 0 le plus proche. Un BFS multisource lancé simultanément depuis tous les 0 fournit la solution optimale en O(mn). Initialisez la file avec toutes les cellules contenant un 0 à la distance 0 et toutes les cellules contenant un 1 avec une distance infinie. BFS propage les distances vers l’extérieur depuis les 0 et définit la distance de chaque cellule contenant un 1 dès qu’elle est atteinte pour la première fois, ce qui garantit qu’il s’agit de la plus courte.
from collections import deque
def update_matrix(mat):
rows, cols = len(mat), len(mat[0])
dist = [[float('inf')] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c))
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols:
if dist[r][c] + 1 < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
mat = [[0,0,0],[0,1,0],[1,1,1]]
result = update_matrix(mat)
for row in result: print(row) # [[0,0,0],[0,1,0],[1,2,1]]Vérification rapide
Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation abordés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : le BFS pour les plus courts chemins dans les graphes non pondérés, avec le suivi des parents pour reconstruire l’itinéraire, l’échelle de mots comme exemple classique de BFS sur un graphe implicite, le BFS bidirectionnel pour les grands graphes et le BFS multisource pour les problèmes comportant plusieurs points de départ. Ensuite, vous appliquerez DFS aux composantes connexes et au remplissage par propagation.
Questions Fréquemment Posées
La leçon « BFS : plus court chemin et parcours par niveaux » est-elle gratuite ?
Oui — le texte complet de « BFS : plus court chemin et parcours par niveaux » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « BFS : plus court chemin et parcours par niveaux » ?
Utilisez BFS pour trouver le plus court chemin dans un graphe non pondéré, résolvez word-ladder niveau par niveau et clonez un graphe avec une table de hachage. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « BFS : plus court chemin et parcours par niveaux » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Représentations des graphes et préparation des parcours
- BFS : plus court chemin et parcours par niveaux
- DFS : composantes connexes et remplissage
- Détection de cycles dans les graphes orientés et non orientés