Cycle detection

O(V + E)

A cycle is a path that returns to where it started without reusing an edge. To detect one in an undirected graph, run DFS and remember each vertex's parent in the search tree. While exploring a vertex's neighbours, if you meet one that's already been visited and isn't the immediate parent, that edge closes a cycle. If DFS finishes every component without hitting such a back edge, the graph is acyclic (a forest). It runs in O(V + E) and is the basis of deadlock detection, spanning-tree checks, and "is this a tree?".

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Edit the input and press Play

How it works

  1. DFS from any vertex, recording each vertex's parent.
  2. For each neighbour, recurse into unvisited ones.
  3. If a neighbour is already visited and isn't the parent, a back edge closes a cycle.
  4. If DFS drains every component with no back edge, the graph is acyclic.

Pseudocode

1hasCycle(graph):                     # O(V + E)2  dfs(u, parent):3    mark u visited4    for v in neighbours(u):5      if v not visited:6        if dfs(v, u): return true7      else if v ≠ parent:8        return true                   # back edge closes a cycle9    return false10  run dfs from every unvisited vertex