AlgoScope

Cycle Detection

Undirected: an edge to a seen vertex other than the parent. Directed: an edge to a vertex still on the DFS path.

Graph traversal, algorithm, intermediate
Enter 1 from 0.012345
Enter 1 from 0.012345

DFS Checks: An undirected cycle

Decision, step 2 of 8

At 0, edge to 1. 1 is unseen, so enter it with parent 0.

How dfs checks works

Cost

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Before this

Variants

  • Undirected (DFS or Union-Find)Back edge to a non-parent.
  • Directed (DFS colours)Grey-to-grey edge.

Leads to

Topics that need this one first.

Taught by the same lesson

DFS Checks covers these too, in the same run.