BFS pour les plus courts chemins non pondérés
Calculer la distance couche par couche depuis une source
BFS pour les plus courts chemins non pondérés est une leçon Coding 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Ce que fait BFS
BFS explore un graphe par couches : d’abord le point de départ, puis tout ce qui se trouve à une étape, ensuite à deux étapes, et ainsi de suite. 🌊
Pourquoi les couches donnent les plus courts chemins
Comme BFS termine chaque couche avant de passer à la suivante, la première fois qu’il atteint un nœud correspond au plus court chemin non pondéré jusqu’à ce nœud.
La file est le moteur
BFS utilise une file : premier entré, premier sorti. Vous ajoutez les nouveaux voisins à l’arrière et traitez ensuite celui qui se trouve à l’avant.
from collections import deque
q = deque([start])Suivre les nœuds déjà vus
Conservez un marqueur visité afin de ne jamais ajouter deux fois le même nœud à la file. Cela permet à BFS de rester rapide et de terminer.
visited = [False] * (n + 1)
visited[start] = TrueStocker la distance
Un tableau de distance contient la couche de chaque nœud. Le point de départ reçoit 0 ; chaque voisin reçoit une valeur supérieure de 1 à celle de son parent.
dist = [-1] * (n + 1)
dist[start] = 0Retirer le premier élément
À chaque étape, prenez le nœud situé à l’avant de la file. C’est le nœud non traité le plus proche : vous devez donc vous en occuper maintenant.
u = q.popleft()Développer les voisins
Pour chaque voisin de u qui n’a pas encore été visité, marquez-le, définissez sa distance et ajoutez-le à l’arrière de la file.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)La boucle complète
Continuez à retirer des éléments et à développer les voisins tant que la file n’est pas vide. Lorsqu’elle est vide, vous avez visité chaque nœud accessible.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Marquer lors de l’ajout
Définissez visited au moment où vous ajoutez le nœud à la file, et non lorsque vous le retirez. Un marquage tardif laisse des doublons entrer dans la file.
Les nœuds inaccessibles restent à -1
Tout nœud dont la distance vaut encore -1 après BFS est simplement inaccessible depuis votre point de départ. Cette réponse est elle aussi pertinente.
BFS est linéaire
BFS parcourt chaque nœud et chaque arête une fois, ce qui donne une complexité en O(n + m). Cela suffit largement pour la plupart des limites des concours.
Vérification rapide
Pourquoi BFS classique donne-t-il les plus courts chemins ?
Récapitulatif
Vous exécutez BFS avec une file et un tableau de distances : marquez les nœuds lors de leur ajout, développez leurs voisins et lisez les distances minimales à la fin. 🎉
Questions Fréquemment Posées
La leçon « BFS pour les plus courts chemins non pondérés » est-elle gratuite ?
Oui — le texte complet de « BFS pour les plus courts chemins non pondérés » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « BFS pour les plus courts chemins non pondérés » ?
Calculer la distance couche par couche depuis une source Tu pratiques Coding 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding 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 pour les plus courts chemins non pondérés » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding 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
- Listes d’adjacence à partir de l’entrée
- BFS pour les plus courts chemins non pondérés
- DFS, récursion et piles itératives
- Composantes connexes et remplissage par diffusion