Graph Traversal (BFS & DFS)

How do you "Walk" through a graph without getting stuck in a loop? You must choose between exploring Wide (Breadth-First) or Deep (Depth-First). Both use an O(V + E) time complexity.

1. Breadth-First Search (BFS)

Explores neighbors level-by-level. It uses a Queue (FIFO). BFS is guaranteed to find the Shortest Path in an unweighted graph (e.g., "Find the minimum number of connections between two users on LinkedIn").

2. Depth-First Search (DFS)

Explores as far as possible down one branch before backtracking. It uses a Stack (LIFO) or Recursion. DFS is perfect for finding "Dead Ends," performing Topological Sorts, or solving Puzzles/Mazes.

3. The 'Visited' Set

In both algorithms, you MUST keep a HashSet of 'Visited' nodes. Unlike trees, graphs can have Cycles. Without a visited list, your code will enter an infinite loop and crash your server.

4. Interview Mastery

Q: "How do you detect a cycle in a Directed Graph?"

Architect Answer: "We use DFS with three states for each node: **Unvisited**, **Visiting** (currently in the recursion stack), and **Visited**. If we encounter a node that is currently in the 'Visiting' state, we have found a **Back-Edge**, which means a cycle exists. This is the foundation of 'Cycle Detection' in build systems and dependency managers."