Graph Techniques
DFS and BFS are foundational for solving graph problems, with cycle detection and topological sort being key techniques frequently tested in interviews. Cycle detection identifies whether a graph contains cycles, crucial for problems involving dependencies. The method varies for directed and undirected graphs, emphasizing the need to clarify graph type before implementation. Topological sort, applicable only to directed acyclic graphs, provides a linear ordering of nodes based on dependencies. Both techniques are interconnected, addressing the existence of valid orderings in graph-related problems, making them 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
...