Laboratoire Python Interactif

Breadth-First Search

Le playground s'exécute automatiquement au chargement. Cliquez sur Exécuter mon code pour tracer votre propre Python — chaque étape animée en direct.

Expliquer·Ligne par ligne

Rejouer·Étape par étape

Défi·Indices guidés

XP·...

Pipeline de Flux de Données

advanced Parcours

Bubble Sort

Two Sum

Valid Parentheses

Merge Sort

Quick Sort

Heap Sort

Breadth-First Search

Depth-First Search

Binary Tree Traversal

Fibonacci (Recursive)

Expliquer

Line 16

graph defined: 4 nodes (0-3), directed edges. Starting BFS from node 2.

Pourquoi cette approche ?

The graph is represented as an adjacency list — a dict mapping each node to its list of neighbors. This representation is O(V+E) space and makes neighbor lookup O(degree), which is efficient for sparse graphs.

Structured Explanation

Overview

La recherche en largeur d'abord (BFS) explore un graphe niveau par niveau, visitant tous les voisins avant de passer aux nœuds plus lointains.

Analogy

Comme répandre de l'eau dans un labyrinthe — elle s'étend uniformément dans toutes les directions simultanément.

Step-by-step

Commence depuis le nœud source, marque-le visité
Ajoute-le à une file
Retire de la file, visite tous ses voisins non visités
Ajoute les voisins à la file et répète

Visual

Graphe: A-B, A-C, B-D BFS depuis A: A → B,C → D File: [A] → [B,C] → [C,D] → [D]

Common mistakes

Oublier de marquer les nœuds comme visités → boucle infinie
Utiliser une pile au lieu d'une file (c'est DFS)

Practice questions

Trouve le chemin le plus court dans un graphe non pondéré
Vérifie si un graphe est biparti

Time

O(V + E)

Space

O(V)

Complexité

Temps

O(V + E)

Espace

O(V)

Aperçu de la Complexité

O(1)

O(log n)

O(n)temps

O(n log n)

O(n²)

n = 8plage 1-20

POUR N = 8

Complexité	Opérations
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Défi

Parcours en largeur (BFS)

Indice

Explore le graphe niveau par niveau avec une file.

Studio de Code

Breadth-First Search

Monaco Prêt

Python Prêt

lesson.pyline 16

Loading editor...

Console de Sortie

0 lines

Pas encore de sortie...

Chronologie

Structures de Données

Pile d'appels (Primitives & Références)

graphobj

VALEUR PILE

{0:[1,2], 1:[2], 2:[0,3], 3:[3]}

startint

VALEUR PILE

2

Applications du Monde Réel

1

Plus court chemin dans un graphe non pondéré

2

Degrés de séparation en réseau social

3

Découverte de pages dans un robot d'exploration

Comments

Loading comments...