Saltar al contenido principal
Data structures, algorithms, and the core CS foundations — plus an optional advanced track for expert topics.

Core Computer Science

Data structures, algorithms, and the core CS foundations — plus an optional advanced track for expert topics.

Graph Algorithms Visualizer

BFS — Breadth-First Search

Time O(V + E) · Space O(V)
Paso 0 / 0
Speed 100ms
Step Progress 0 / 0
Visited 0
Frontier 0
Status Ready
Unvisited
Start
Active
Visited
MST / SPT
Rejected
SCC component

Queue

Step Explanation

Select an algorithm and press Play to begin.

Pseudocode 
 
 
 
 
  
 
 
Graph Traversal (BFS & DFS)
   
 
  Elementary (2/5)
 
~45 minutos   BFS: level-order traversal  DFS: depth-first exploration  Queue vs Stack  Visited set para evitar ciclos  
Prereqs: Grafos básicos, Colas y pilas  
 
Quick Reference
Breadth-First Search
BFS is a graph traversal algorithm that explores all vertices reachable from a source, visiting neighbors level by level using a FIFO queue.

Difficulty: Elementary (2/5)
graph
Complexity
Best Time
O(V + E)
Average Time
O(V + E)
Worst Time
O(V + E)
Space
O(V)
When to Use
Use BFS when you need the shortest path in an unweighted graph, level-order traversal, or connectivity checks.
Pros
  • Guarantees shortest path in unweighted graphs
  • Systematic level-by-level exploration
  • O(V+E) time complexity
Cons
  • Requires O(V) memory for the queue
  • Not suitable for weighted shortest paths
  • May explore many irrelevant nodes for deep targets
History
BFS was invented in the 1950s by Edward F. Moore as part of his work on maze-solving algorithms.
 
 
Graph Traversal explora todos los nodos de un grafo sistemáticamente usando BFS (Breadth-First Search) o DFS (Depth-First Search). Ambas son O(V + E) pero tienen comportamientos muy distintos.


BFS explora por niveles (como olas); DFS se hunde hasta el fondo antes de retroceder (como un laberinto).


Cómo Funciona


BFS


    

  1. Inicializa queue con nodo fuente, visited[fuente] = true.
    2. 

  2. Mientras queue no esté vacía:

      

    • Extrae nodo u.
      • 

    • Por cada vecino v de u: si no visitado, marca y encola.
      • 

    

    3. 



DFS


    

  1. Inicializa stack con nodo fuente, o recursión.
    2. 

  2. Marca nodo como visitado.
    3. 

  3. Por cada vecino no visitado: recursión DFS.
    4. 



Idea Clave


BFS usa una queue (FIFO): explora todos los nodos a distancia d antes que los de distancia d+1. Eso garantiza shortest path en grafos sin peso.


DFS usa un stack (LIFO) o recursión (call stack): se hunde hasta un dead end, luego retrocede. No garantiza shortest path.


Ejemplo Trabajado


Grafo:


0: 1, 2
1: 0, 3, 4
2: 0, 5
3: 1
4: 1, 5
5: 2, 4


Fuente: 0.


BFS orden: 0, 1, 2, 3, 4, 5 (por niveles).
DFS orden: 0, 1, 3, 4, 5, 2 (depende de orden de vecinos).


Casos Extremos y Trampas


    

  • Grafo con ciclos — visited set es crítico para evitar loops infinitos.
    • 

  • Grafo desconectado — itera sobre todos los nodos como fuente para connected components.
    • 

  • Directed graph — DFS no puede ir en reversa a menos que guardes aristas reversas.
    • 

  • BFS para shortest path — solo funciona en unweighted graphs.
    • 



Comparación

























AlgoritmoEstructuraOrdenShortest path (unweighted)
BFSQueuePor nivelesSí
DFSStack/RecursionPor profundidadNo


Aplicaciones


    

  • Shortest path — BFS en redes sociales (grados de separación)
    • 

  • Cycle detection — DFS en directed graphs
    • 

  • Topological sort — DFS con post-order
    • 

  • Connected components — BFS/DFS desde cada nodo no visitado
    • 

  • Maze solving — DFS para backtracking, BFS para shortest exit
    • 



Trayectoria de Práctica


    

  1. Implementa BFS y DFS; traza el ejemplo en el visualizador.
    2. 

  2. Verifica BFS shortest path en unweighted graph.
    3. 

  3. Implementa connected components: cuenta cuántos componentes conexos.
    4. 

  4. Investiga bidirectional BFS: ¿por qué reduce el search space?
    5. 

  5. Investiga DFS para topological sort: ¿por qué post-order reverse?
    6.