Skip to content
Tutorials Center
My learning

Topics

Lesson 127 of 225 ยท Graphs

Cycle Detection

Detect cycles in undirected graphs with the parent trick, in directed graphs with three colors, and in functional graphs with Floyd's tortoise and hare.

A cycle is a path that starts and ends at the same vertex without reusing an edge. Cycles are sometimes the thing you want to find (a loop in a road network) and sometimes the thing you must rule out. A build system with a cycle of dependencies can never finish, a spreadsheet with a cell that depends on itself has no answer, and two threads that each wait for the other are deadlocked. All three are the same question: does this graph contain a cycle?

The question has a different answer technique depending on the kind of graph. In an undirected graph, you must be careful not to mistake "I came from there" for a cycle. In a directed graph, you must tell "already finished" apart from "still on my current path". And in a graph where every vertex has exactly one outgoing edge, a neat two-pointer trick finds the cycle in O(1) extra space. This lesson covers all three. It builds on depth-first search and the graph representations you already know.

What counts as a cycle

TEXT
undirected                    directed

  A --- B                      A --> B
   \   /                       ^     |
     C        cycle A-B-C      |     v
                               D <-- C     cycle A -> B -> C -> D -> A

  A --- B     no cycle         A --> B --> D
  |                            |           ^
  C                            +-----> C --+     no cycle (a DAG)

Notice the last picture: A reaches D by two different routes, but you can never get back to A. That is not a cycle. A directed graph without cycles is a DAG (directed acyclic graph), and only DAGs can be topologically sorted.

Undirected graphs: the parent trick

Run a DFS. If you ever step onto a vertex you have already visited, you have found a second route to it, which means a cycle. There is one catch. In an undirected graph, the edge A - B is stored in both directions. When you go from A to B and look at B's neighbors, A is among them and A is visited. That is just the edge you came along, not a cycle.

The fix is to remember each vertex's parent, the vertex we arrived from, and ignore that single edge back. A visited neighbor that is not the parent means a cycle.

Python Undirected cycle detection with parent tracking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The outer for loop matters: the graph may be in several pieces (components), and the cycle may sit in any of them. The cost is O(V + E) time and O(V) space.

The parent check assumes there is at most one edge between two vertices. If your input can contain parallel edges (two separate roads between the same pair of towns), those two edges form a cycle of length 2, and skipping every edge to the parent hides it. In that case, compare edge ids instead of parent vertices.

A counting shortcut

A graph with no cycles is a forest, and a forest with V vertices and C components has exactly V - C edges. Any extra edge closes a cycle. So you can detect a cycle without searching for it at all: count components, and compare.

Python Edge counting: forest or not?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This uses the fact that a simple undirected graph with V vertices, E edges and C components has a cycle exactly when E > V - C.

With union-find

If edges arrive one at a time, union-find is the natural tool. Before adding an edge (a, b), ask whether a and b are already in the same set. If yes, the new edge would close a cycle. That is exactly the "redundant connection" problem, and it is also the heart of Kruskal's algorithm for minimum spanning trees.

Directed graphs: three colors

The parent trick fails for directed graphs, and so does a plain visited set. Look at the diamond DAG from above: A leads to B and C, and both lead to D. A DFS visits D through B, finishes it, comes back, goes into C, and sees D again, already visited. A naive "seen before means cycle" rule would shout "cycle!", but there is none.

The real difference is where the visited vertex is. A directed cycle exists exactly when DFS finds an edge from the current vertex to a vertex that is still on the current path (an ancestor that has not finished yet). Edges to vertices that are completely finished are harmless.

So each vertex gets one of three colors:

  • white: not discovered yet,
  • gray: discovered, still exploring its descendants (it is on the recursion stack),
  • black: finished; everything reachable from it has been explored.

An edge into a gray vertex is a back edge, and a back edge means a cycle.

Python Directed cycle detection with colors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Walk through loop: DFS goes 0, 1, 2, 3 and turns them all gray. From 3 it looks at neighbor 1, which is gray, so the path from 1 onward, 1, 2, 3, plus 1 again, is a cycle. In the diamond, by the time C looks at D, D is black, so it is ignored.

Each vertex is colored three times at most and each edge examined once: O(V + E) time. The recursion stack and colors take O(V) space. For very deep graphs you can convert this to an explicit stack, or use the next approach.

Kahn's algorithm as a cycle detector

A directed graph has a cycle if and only if it cannot be fully topologically sorted. Kahn's algorithm repeatedly removes vertices with no incoming edges. If it gets stuck with vertices left over, those vertices are on cycles or are reachable from cycles. This avoids recursion entirely, which is why many production tools use it to check dependency graphs.

Cycles in a functional graph

A functional graph is a directed graph in which every vertex has exactly one outgoing edge. A single array describes it: nxt[i] is where vertex i points. Following the arrows from any start, you must eventually repeat a vertex, so the walk looks like the Greek letter rho: a tail leading into a loop.

TEXT
nxt = [1, 2, 3, 4, 5, 3]

  0 -> 1 -> 2 -> 3 -> 4
                 ^    |
                 |    v
                 +--- 5

tail: 0 1 2        cycle: 3 4 5 (length 3)

You could walk and remember every visited vertex in a set, which costs O(n) memory. Floyd's tortoise and hare does it in O(1) memory. Move slow one step and fast two steps per round. If there is a cycle, the fast pointer laps the slow one inside it, and they meet. Then:

  1. To find the start of the cycle: put one pointer back at the beginning and move both one step at a time. They meet at the cycle start.
  2. To find the length: from the start, walk until you return.

This is the same idea as detecting a loop in a linked list.

Python Floyd's tortoise and hare

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Phase 2 works because of some arithmetic. If the tail has length t and the loop has length L, then at the first meeting the slow pointer has moved k steps and the fast one 2k. The difference k is a multiple of L. Walking t more steps from the start of the whole walk, and t more steps from the meeting point, both pointers land on the cycle entrance. You do not need to remember the proof to use it, but it is a good one to try on paper.

A classic problem: find the duplicate

Given an array of n + 1 integers, each between 1 and n, exactly one value appears at least twice. Find it without modifying the array and in O(1) extra space.

The brute force compares every pair, O(n^2). Sorting or a set drops the time to O(n log n) or O(n), but sorting changes the array and a set needs O(n) memory. The trick is to read the array as a functional graph, i -> nums[i]. Because values are in 1..n, nothing points to index 0, so starting there is safe. Two different indexes holding the same value both point to the same vertex, so that vertex has two incoming edges, and it is exactly the entrance of the cycle.

Python Find the duplicate number

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both approaches agree. The Floyd version uses O(1) space and O(n) time.

Which technique do I use?

Graph Technique Time Extra space
Undirected DFS with parent (or edge count, or union-find) O(V + E) O(V)
Directed DFS with three colors, or Kahn's algorithm O(V + E) O(V)
Functional (one out-edge each) Floyd's tortoise and hare O(n) O(1)

Common mistakes

  • Using the undirected rule on a directed graph. A plain visited set reports cycles in every DAG that has two paths to the same vertex.
  • Forgetting to turn gray into black. If you never recolor a vertex after finishing it, a harmless cross edge looks like a back edge.
  • Starting from one vertex only. A graph may be disconnected; loop over all vertices.
  • Ignoring self loops. An edge v -> v is a cycle of length 1. The color method catches it, since v is gray when it looks at itself.
  • Recursing too deep. Python's default recursion limit is about 1,000 frames. A chain of 5,000 vertices needs an explicit stack.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does an undirected DFS need to remember each vertex's parent?

    Each undirected edge is stored in both directions, so the parent shows up as a visited neighbor. Without ignoring it, every edge would look like a cycle.
  2. 2. In directed-cycle detection with three colors, which kind of edge proves that a cycle exists?

    A gray vertex is an ancestor still on the current path. An edge back to it closes a loop. Edges to black (finished) vertices only reach already explored territory.
  3. 3. A simple undirected graph has 8 vertices, 3 components and 6 edges. Does it contain a cycle?

    A forest with 8 vertices and 3 components has exactly 5 edges. With 6 edges, one edge is extra and must close a cycle.
  4. 4. Floyd's algorithm detects a cycle in a functional graph using which amount of extra memory?

    Only two pointers (slow and fast) are stored, so extra memory is constant.
  5. 5. A directed graph has edges A -> B, A -> C, B -> D and C -> D. What does a correct detector report?

    Two paths to the same vertex are fine in a DAG. A cycle needs a way to return to a vertex already on the current path, and there is none here.

Summary

  • A cycle is a closed path; a graph without cycles is a forest (undirected) or a DAG (directed).
  • Undirected: DFS and ignore the parent edge; any other visited neighbor means a cycle. Equivalent tests: edges > V - components, or union-find finds both ends already joined.
  • Directed: use three colors; an edge to a gray vertex (still on the current path) is a back edge and proves a cycle. Kahn's algorithm gives the same answer without recursion.
  • Functional graphs: Floyd's tortoise and hare finds the cycle, its start and its length with O(1) memory; the same trick finds the duplicate number in an array.
  • All graph-search detectors run in O(V + E) time; remember to start a search from every unvisited vertex.

Next: Topological Sort