Cycle detection

Prerequisites

• DFS and recursion.
• Directed graphs.
• Union-Find, for the undirected method.

The analogy

How it works

Precondition: the colour method below is for directed graphs. For undirected graphs, use Union-Find, or DFS that ignores the edge back to the parent.

Start with one DFS by hand

Directed edges: 0 → 1, 1 → 2, 2 → 0, 2 → 3. All vertices start white. Start DFS at 0, colour a vertex grey when you enter it and black when you leave. Predict, then open "Check".

Finish the picture: the undirected case

Undirected edges A–B, B–C, C–A. Use Union-Find: for each edge, check whether its ends are already in the same group.

• A–B, then B–C. Predict the groups.
  Check

  A–B: different groups, merge {A, B}. B–C: different, merge {A, B, C}.

• C–A. Predict the result.
  Check

  C and A are already in the same group, so this edge closes a cycle.

The rule in plain words

Directed: run DFS from every white vertex. Colour grey on entry and black on exit; an edge to a grey vertex is a back edge, which means a cycle.

Undirected: process edges with Union-Find; an edge whose ends are already connected closes a cycle.

The code

Read this code after you have done the DFS by hand. It will make more sense.

int has_cycle_from(int adj[][4], int n, int u, int color[]) {   /* 0 white, 1 grey, 2 black */
    color[u] = 1;                                     /* on the current path */
    for (int v = 0; v < n; v++) {
        if (!adj[u][v]) continue;
        if (color[v] == 1) return 1;                  /* back edge: cycle */
        if (color[v] == 0 && has_cycle_from(adj, n, v, color)) return 1;
    }
    color[u] = 2;                                     /* fully explored */
    return 0;
}

int has_cycle(int adj[][4], int n, int color[]) {     /* color[] starts all 0 */
    for (int u = 0; u < n; u++)
        if (color[u] == 0 && has_cycle_from(adj, n, u, color)) return 1;
    return 0;
}

flowchart TD
  A["colour u grey"] --> B{"next neighbour v?"}
  B -->|"v is grey"| C["cycle found"]
  B -->|"v is white"| D["explore v"]
  B -->|"v is black"| B
  D --> B
  B -->|"no more neighbours"| E["colour u black, return"]
          

How fast is it?

It is a DFS with a constant-time colour check per edge:

Common mistakes

• Using a single "visited" flag on a directed graph and reporting false cycles.
• In undirected DFS, treating the edge back to the parent as a cycle.
• Running DFS only from vertex 0 and missing cycles in other parts of the graph.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• An edge to a grey vertex means a cycle because grey vertices form the current path, so the edge closes a loop.
• Edges to black vertices are safe because a finished vertex cannot reach the current path.
• It costs $O(V + E)$ because it is a single DFS with constant work per edge.
• Undirected graphs can use Union-Find because an edge inside one component closes a cycle.
• DFS restarts from every white vertex because a cycle may be in a part not reachable from the first start.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is DFS cycle detection like unrolling a thread through a building?
   Sample answer

   The thread marks your current path; if you reach a room where the thread already lies, you've walked in a circle.

2. Walk through the colour DFS on 0 → 1, 1 → 2, 2 → 0, 2 → 3.
   Sample answer

   0, 1, 2 become grey along the path; at 2 the edge 2 → 0 points to grey 0, so there is a cycle 0 → 1 → 2 → 0.

3. Why does the code colour u black only after the loop?

   A good answer says what grey must represent.

   Sample answer

   Grey must mean "still on the current path". u stays on the path until all its neighbours are explored; marking it black earlier would hide back edges to it.

4. So when does a directed graph have a cycle, in one sentence?
   Sample answer

   Exactly when a DFS finds an edge to a vertex that is still on the current DFS path.

5. Why aren't two colours enough for directed graphs?

   A good answer gives the 0 → 1, 0 → 2, 1 → 2 example.

   Sample answer

   Vertex 2 is reached twice there without any cycle. A plain "visited" flag can't tell a back edge (cycle) from an edge into a finished branch.

6. What does cycle detection cost?
   Sample answer

   $O(V + E)$ with DFS; $O(E \, \alpha(V))$ with Union-Find on undirected graphs.

7. How would you detect a cycle in an undirected graph?
   Sample answer

   Union-Find over the edges (an edge inside one group is a cycle), or DFS where reaching a visited vertex other than your parent means a cycle.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the undirected variants and the deadlock story. I'd keep the thread analogy, the 0 → 1 → 2 → 0 example, and "edge to a grey vertex means a cycle, $O(V + E)$".

External resources

• VisuAlgo: DFS: watch DFS classify tree and back edges.
• GeeksforGeeks: Detect a cycle in a directed graph: the colour method with code.
• Wikipedia: Cycle (graph theory): definitions and detection methods.

Videos

• YouTube search: cycle detection with DFS: pick a walkthrough of the three colours.