Graph Techniques
DFS and BFS are foundational techniques in graph problem-solving, with cycle detection and topological sort being critical for handling dependencies and ordering in directed graphs. Cycle detection identifies if a graph contains cycles, which indicates circular dependencies, while topological sort provides a linear ordering of nodes in directed acyclic graphs. Both techniques have specific implementations and complexities, and recognizing their relevance in problems involving task completion or ordering is essential for effective problem-solving in coding interviews.
DFS and BFS form the foundation of graph problem-solving, but two techniques built on top of them appear frequently in coding interviews: cycle detection and topological sort. Both are unique to graphs, both are commonly tested directly, and neither can be derived from first principles quickly under interview pressure.
Interview lens: Cycle detection and topological sort are almost always the answer to problems involving dependencies, ordering, or validity of a directed graph. When a problem asks whether something is possible given a set of constraints, or what order tasks must be completed in, one of these two techniques is almost certainly involved.
Cycle detection
Cycle detection determines whether a graph contains a cycle: a path that starts and ends at the same node. The approach differs depending on whether the graph is directed or undirected, and getting that distinction wrong produces incorrect results without raising an error.
For undirected graphs, DFS detects a cycle when it encounters a neighbor that has already been visited and is not the parent of the current node. The parent check is necessary because in an undirected graph, every edge appears in both directions. Without it, we would incorrectly flag every edge as a back edge.
For directed graphs, DFS uses two states instead of one: visited and in the current recursion stack. A cycle exists when DFS encounters a node that is already in the current recursion stack. A node that has been fully processed and removed from the stack is not a cycle, even if it has been visited before.
Trap (using the same approach for directed and undirected graphs): Applying the undirected cycle detection approach to a directed graph produces false positives. In a directed graph, a node can be visited multiple times via different paths without forming a cycle. The cycle only exists when a back edge points to a node currently on the recursion stack. Always ask the interviewer whether the graph is directed before writing the cycle detection logic.
Time and space complexity
Time
...