Sign in to track progress and bookmarks.
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.
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").
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.
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.
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."
Quizzes linked to this course—pass to earn certificates.
On this page
1. Breadth-First Search (BFS) 2. Depth-First Search (DFS) 3. The 'Visited' Set 4. Interview Mastery