Graph Traversal

Breadth-First Search (BFS)

BFS explores the graph level by level, visiting all neighbors of a vertex before moving to the next level. It uses a queue.

Algorithm:
1. Start at source vertex, mark as visited
2. Enqueue the source
3. While queue is not empty:
   a. Dequeue a vertex v
   b. For each unvisited neighbor u of v:
      Mark u as visited
      Enqueue u

Time Complexity: O(V + E)
Space Complexity: O(V)

Applications:
  Shortest path in unweighted graphs
  Level-order traversal
  Finding connected components

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion).

Algorithm:
1. Start at source vertex, mark as visited
2. For each unvisited neighbor u:
   DFS(u)

Iterative version using stack:
1. Push source to stack
2. While stack is not empty:
   a. Pop vertex v
   b. If not visited:
      Mark as visited
      Push all unvisited neighbors

Time Complexity: O(V + E)
Space Complexity: O(V)

Applications:
  Cycle detection
  Topological sorting
  Finding connected components
  Solving mazes

BFS vs DFS

BFS:                          DFS:
  Uses Queue                     Uses Stack/Recursion
  Explores level by level        Explores branch by branch
  Finds shortest path            May not find shortest path
  Better for nearby targets      Better for deep exploration
  Uses more memory               Uses less memory