Skip to content

BreadthFirstSearch

Jump to bottom
krishanthan4 edited this page Dec 16, 2025 · 1 revision

Breadth First Search (BFS)

Problem Description

Implement breadth-first search for graph traversal. BFS explores all neighbors at the current depth before moving to nodes at the next depth level.

What is BFS?

BFS is a graph traversal algorithm that explores all nodes at the present depth before moving to nodes at the next depth level.

Characteristics

  • Time Complexity: O(V + E) where V is vertices and E is edges
  • Space Complexity: O(V) for the queue and visited set
  • Traversal Strategy: Explore level by level
  • Implementation: Queue (FIFO)
  • Key Property: Finds shortest path in unweighted graphs

How It Works

  1. Start at a given node and mark it visited
  2. Add it to a queue
  3. While queue is not empty:
    • Dequeue a node
    • Visit all unvisited neighbors
    • Mark them visited and enqueue them
  4. Repeat until queue is empty

Your Task

Implement the following methods in Breadth_First_Search.java:

  1. bfs(Map<Integer, List<Integer>> graph, int start) - Basic BFS traversal
  2. shortestPath(Map<Integer, List<Integer>> graph, int start, int end) - Find shortest path

Graph Representation

The graph is represented as an adjacency list:

Map<Integer, List<Integer>>
Key: vertex
Value: list of adjacent vertices

Test Cases to Consider

  • Single node graph
  • Path exists between start and end
  • No path exists between start and end
  • Start equals end
  • Disconnected components
  • Multiple shortest paths (return any one)

Hints

  • Use a Queue (LinkedList in Java works well)
  • Use a Set to track visited nodes
  • For shortest path: track parent/predecessor of each node
  • Mark nodes as visited when you enqueue them, not when you dequeue

Applications

  • Shortest path in unweighted graphs
  • Level order traversal of trees
  • Finding connected components
  • Web crawling
  • Social network connections (friends at distance k)
  • GPS navigation

Follow-up Questions

  1. Why does BFS find the shortest path in unweighted graphs?
  2. How would you modify BFS for weighted graphs? (Hint: Dijkstra's)
  3. How would you find all nodes at distance k from a source?
  4. What's the memory trade-off between BFS and DFS?

BFS vs DFS

Aspect BFS DFS
Data Structure Queue Stack/Recursion
Memory More (stores level) Less (stores path)
Shortest Path Yes (unweighted) No
Use Case Level-wise, shortest path Path finding, cycles

Common Pitfalls

  • Not marking nodes as visited when enqueueing (causes duplicates)
  • Using wrong data structure (Stack instead of Queue)
  • Not handling disconnected graphs
  • Forgetting to check if start node exists

Related Algorithms

  • Depth First Search (DFS)
  • Dijkstra's Algorithm (weighted shortest path)
  • A* Search Algorithm
  • Bidirectional Search

Clone this wiki locally