BFS 0-1 avec une deque
Trouver les plus courts chemins lorsque les poids valent 0 ou 1
BFS 0-1 avec une deque 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.
Un type particulier de graphe
Certains graphes n'ont que des arêtes de poids 0 ou 1. Dans ce cas, vous pouvez faire mieux que Dijkstra grâce à une astuce plus simple et plus rapide.
Découvrez BFS 0-1
BFS 0-1 trouve les plus courts chemins dans les graphes dont les poids valent 0 ou 1 en temps linéaire, sans tas ni facteur logarithmique.
L'outil : une file à double extrémité
Remplacez le tas par une file à double extrémité, une file dans laquelle vous pouvez insérer et retirer des éléments à l'avant comme à l'arrière.
from collections import deque
dq = deque([src])L'idée fondamentale
Une arête de poids 0 conserve la même distance, tandis qu'une arête de poids 1 en ajoute une. La file à double extrémité maintient ces deux groupes dans le bon ordre.
L'avant pour les arêtes de poids nul
Vous traversez une arête de poids 0 ? Utilisez appendleft pour insérer le voisin à l'avant afin qu'il soit traité ensuite, puisqu'il n'ajoute aucune distance.
dq.appendleft(v)L'arrière pour les arêtes de poids un
Vous traversez une arête de poids 1 ? Utilisez append pour insérer le voisin à l'arrière, car il se trouve à un niveau de plus de la source.
dq.append(v)Retirer depuis l'avant
Retirez toujours le nœud courant avec popleft. La file reste ainsi triée par distance, comme dans un BFS organisé par niveaux.
u = dq.popleft()Relâcher avec le poids
Relâchez chaque arête : calculez une nouvelle distance égale à dist[u] plus le poids de l'arête, puis insérez le voisin à l'avant ou à l'arrière selon ce poids.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndPourquoi la file reste triée
La file contient au plus deux distances distinctes à la fois. Cet invariant explique précisément pourquoi l'insertion à l'avant ou à l'arrière fonctionne.
La vitesse linéaire
Comme il n'y a pas de tas, BFS 0-1 s'exécute en O(V + E), ce qui est nettement plus rapide que Dijkstra sur le même graphe.
Quand l'utiliser
Utilisez-le lorsque les déplacements sont gratuits ou coûtent un, par exemple dans les grilles où certaines étapes sont bloquées et d'autres accessibles.
Vérification rapide
Vous relâchez un voisin en traversant une arête de poids 0. Où l'insérez-vous ?
Récapitulatif : BFS 0-1
Avec une file à double extrémité, insérez les arêtes de poids 0 à l'avant et celles de poids 1 à l'arrière. Vous obtenez les plus courts chemins en temps O(V+E), de manière claire. ⚡
Questions Fréquemment Posées
La leçon « BFS 0-1 avec une deque » est-elle gratuite ?
Oui — le texte complet de « BFS 0-1 avec une deque » 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 0-1 avec une deque » ?
Trouver les plus courts chemins lorsque les poids valent 0 ou 1 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 0-1 avec une deque » ?
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
- Dijkstra avec un tas
- BFS 0-1 avec une deque
- Bellman-Ford et arêtes négatives
- Floyd-Warshall entre toutes les paires