← Back to the graphs page
Directed Graph (Digraph)
Edges point one way: A → B does not imply B → A. Models dependency, flow, and hierarchy.
What to know
- Each node has separate in-degree and out-degree.
- Cycle detection needs three DFS states (white/gray/black) — a gray→gray edge is a back edge.
- Strongly connected component (SCC): every node reaches every other node within it.
- Reversing all edges (transpose) is a key trick used by Kosaraju’s algorithm.
In the wild: Twitter follows, web page links, import graphs, deadlock detection in databases.
Algorithms to reach for
DFS cycle detection (3-color)
O(V + E)Detect deadlocks / circular dependencies
Kosaraju / Tarjan SCC
O(V + E)Collapse strongly connected components
Kahn’s algorithm (BFS topo sort)
O(V + E)Order tasks by dependency, detect cycles by leftover nodes
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.