Graph Cycle Detection
Use DFS state tracking to detect dependency cycles that make the schedule impossible.
0 of 3 problems solved
Graph Cycle Detection
Use DFS state tracking to detect dependency cycles that make the schedule impossible.
- •Is this really a dependency graph?
- •Would a cycle make the task impossible to finish?
- •Can DFS with visiting states detect that cycle?
Course Schedule is a graph problem about impossible loops. If course A needs B, B needs C, and C needs A, you are trapped forever. DFS can detect that by tracking nodes that are currently in the recursion path. Revisiting a node that is still 'in progress' means you found a cycle.
A back-edge into the current DFS path is the signature of a cycle.
- 1Build a graph of prerequisite edges.
- 2Run DFS from each course that has not been fully processed yet.
- 3Mark nodes as visiting while they are on the current recursion path.
- 4If DFS reaches another visiting node, there is a cycle.
- 5Mark nodes as visited when their subtree is safe.
Using only one visited set is not enough. You need to distinguish 'already finished' from 'currently exploring'.
Find if Path Exists in Graph
BFS or DFS from source. Track visited nodes. Return true the moment you reach the destination.
Critical Connections in a Network
Tarjan's bridge algorithm. Track discovery time and low value per node. An edge is a bridge when the child's low value exceeds the parent's discovery time.