Graph Techniques
Understand core graph techniques such as cycle detection and topological sort essential for solving coding interview problems involving task dependencies and valid orderings. This lesson equips you to identify cycles in directed and undirected graphs and compute valid task sequences using topological sorting algorithms in C++.
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 a compiler 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 currently in the 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 through 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
...