Graph Algorithms

Breadth-First Search (BFS)

A comprehensive guide to understanding and implementing the Breadth-First Search algorithm

What is BFS?

Breadth-First Search (BFS) is a graph traversal algorithm that explores vertices in a breadth-ward motion. It visits all vertices at the current depth level before moving to vertices at the next depth level.

BFS uses a queue data structure to keep track of vertices to visit next, following the First-In-First-Out (FIFO) principle.

Key Characteristics:

  • Explores nodes level by level
  • Uses a queue for vertex management
  • Guarantees shortest path in unweighted graphs
  • Complete algorithm (finds solution if it exists)

Complexity Analysis

Time Complexity: O(V + E)
Space Complexity: O(V)
Best Case: O(1)
Worst Case: O(V + E)

Where V is the number of vertices and E is the number of edges in the graph.

How BFS Works

The BFS algorithm follows these steps:

  1. Initialize: Create a queue and add the starting vertex
  2. Mark as visited: Mark the starting vertex as visited
  3. Process queue: While the queue is not empty:
    • Dequeue a vertex from the front
    • Process the current vertex
    • Add all unvisited neighbors to the queue
    • Mark neighbors as visited
  4. Repeat: Continue until queue is empty

Pseudocode

BFS(graph, start_vertex):
    create empty queue Q
    create empty set visited
    
    Q.enqueue(start_vertex)
    visited.add(start_vertex)
    
    while Q is not empty:
        current = Q.dequeue()
        process(current)
        
        for each neighbor of current:
            if neighbor not in visited:
                visited.add(neighbor)
                Q.enqueue(neighbor)
                
    return visited

Worked Example

Let's trace through BFS on a simple graph:

Graph: A connected to B and C, B connected to D, C connected to E

Starting vertex: A

Step 1: Queue: [A], Visited: {A}

Step 2: Process A, add neighbors B, C

Step 3: Queue: [B, C], Visited: {A, B, C}

Step 4: Process B, add neighbor D

Step 5: Queue: [C, D], Visited: {A, B, C, D}

Step 6: Process C, add neighbor E

Step 7: Queue: [D, E], Visited: {A, B, C, D, E}

Step 8: Process D and E, no new neighbors

Result: Traversal order: A → B → C → D → E

✅ Advantages

  • Optimal for shortest path: Guarantees shortest path in unweighted graphs
  • Complete algorithm: Will find a solution if one exists
  • Level-order traversal: Perfect for exploring by levels
  • Memory efficient: Only stores vertices at current and next level

⚠️ Disadvantages

  • Memory intensive: Can use significant memory for wide graphs
  • Not suitable for deep graphs: May be slower than DFS for very deep graphs
  • No path information: Basic BFS doesn't store path information
  • Infinite graphs: Cannot handle infinite or very large graphs

Common Applications

🗺️ Pathfinding

Finding shortest path in unweighted graphs, GPS navigation systems, maze solving.

🌐 Social Networks

Finding connections, friend suggestions, analyzing social network structures.

🔍 Web Crawling

Systematic exploration of web pages, search engine indexing.

🎮 Game Development

AI pathfinding, level generation, game state exploration.

Common Mistakes to Avoid

❌ Forgetting to mark vertices as visited

This leads to infinite loops and incorrect results. Always mark vertices as visited when adding them to the queue.

❌ Using a stack instead of a queue

This would result in Depth-First Search, not Breadth-First Search. Remember: BFS uses a queue (FIFO).

❌ Not handling disconnected graphs

BFS only explores connected components. For disconnected graphs, you need to run BFS from multiple starting points.

Frequently Asked Questions

Q: When should I use BFS over DFS?

A: Use BFS when you need the shortest path in unweighted graphs, want to explore nodes level by level, or when the solution is likely to be found at a shallow depth.

Q: Can BFS handle weighted graphs?

A: Basic BFS treats all edges as having equal weight. For weighted graphs, use Dijkstra's algorithm or other shortest-path algorithms.

Q: What's the difference between BFS and Dijkstra's algorithm?

A: BFS finds shortest paths in unweighted graphs, while Dijkstra's algorithm handles weighted graphs with non-negative weights.

Q: How much memory does BFS use?

A: BFS uses O(V) space in the worst case, where V is the number of vertices. The queue can contain up to all vertices in the worst case.

Try BFS Visualizer →