AV
LibraryGraph BFS

Graph BFS

Medium

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth before moving to the next level. Useful for finding shortest paths in unweighted graphs.

Time Complexity

O(V + E)

Space Complexity

O(V)

Category

Graph

Introduction to Breadth-First Search (BFS)

BFS is a graph traversal algorithm that explores vertices in layers - first visiting all neighbors, then all neighbors of neighbors. It's essential for finding shortest paths in unweighted graphs and is widely used in real applications.

How It Works

BFS uses a queue (FIFO) to explore the graph:

1. Start with a vertex and add it to queue

2. Mark it as visited

3. While queue is not empty:

- Remove front vertex from queue

- For each unvisited neighbor:

- Mark as visited

- Add to queue

4. Continue until queue is empty

Algorithm Complexity

**Time Complexity**: O(V + E) - Visit each vertex and edge once
**Space Complexity**: O(V) - Queue can hold all vertices in worst case

Key Characteristics

1. Uses queue (FIFO) for processing

2. Explores all neighbors at current distance before moving further

3. Finds shortest path in unweighted graphs

4. Visits nodes level by level

5. Always finds solution if it exists

Advantages

1. Finds shortest paths in unweighted graphs

2. Guarantees finding the minimum distance

3. Can be used for connectivity problems

4. Good for level-order traversal

5. Often faster in practice than DFS

6. Suitable for bipartite checking

Disadvantages

1. Uses more memory than DFS (stores all nodes at current level)

2. Slower for finding connectivity in deep graphs

3. Cannot easily find all paths (unlike DFS)

4. May use more memory for wide graphs

When to Use

**Shortest path**: Finding shortest route in unweighted graphs
**Social networks**: Friend recommendations (distance 2-3)
**Puzzle solving**: Finding minimum moves to solve
**Level-order traversal**: Processing nodes level by level
**Bipartite checking**: Determining if graph is bipartite
**Network broadcast**: Reaching all nodes from source

Applications

GPS navigation (shortest route)
Social media connections (degrees of separation)
Web crawlers (indexing by depth)
Game AI (finding optimal moves)
Network protocols (flooding)
Networking (finding connected components)
Robotics (pathfinding on grids)

Variations

1. **Bidirectional BFS**: Search from both ends

2. **0-1 BFS**: Handle weights of 0 and 1

3. **Multi-source BFS**: Start from multiple vertices

4. **Level-order traversal**: BFS on trees

BFS vs DFS

|---------|-----|-----|

Key Takeaways

  • Explores level by level
  • Uses queue for traversal
  • Finds shortest paths
  • Good for connectivity problems
  • All vertices are explored
  • Guarantees shortest path in unweighted graphs

Implementation

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);
  
  while (queue.length > 0) {
    const v = queue.shift();
    console.log(v);
    
    for (let neighbor of graph[v] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  
  return visited;
}

Tags

graphtraversalqueueintermediate

Quick Stats

Difficulty:Medium
Type:Graph

Share