Cycle detection
Walk the graph depth-first and give every node one of three states: new, on the current path, or finished. An arrow to a finished node is harmless. An arrow back to a node still on the current path closes a loop.
Does following the arrows ever lead back to where you started? Walk depth-first and keep track of the current path.
1function hasCycle(adj) {2 const state = new Array(adj.length).fill('new');3 const visit = (u) => {4 state[u] = 'active';5 for (const v of adj[u]) {6 if (state[v] === 'active') return true;7 if (state[v] === 'new' && visit(v)) return true;8 }9 state[u] = 'done';10 return false;11 };12 return adj.some((_, u) => state[u] === 'new' && visit(u));13}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | V + E | a cycle near the start stops the walk early |
| average | V + E | every node and arrow is looked at once |
| worst | V + E | no cycle: everything gets explored |
| space | V | a state per node, plus the path |
Where it breaks
- Two states are not enough. Pick A diamond: D is reached a second time through C, but that is not a loop. Only "seen or not" would wrongly call it one. "Finished" is what tells a harmless revisit from a real cycle.
- Undirected graphs need a different rule. There every edge goes both ways, so stepping straight back to the node you came from would look like a cycle. Undirected checks ignore the edge to the parent.
- Why it matters. A cycle in task dependencies means the tasks can never all be done. Build tools, spreadsheets and package managers run exactly this check.