Cycle Detection in Graphs

July 2026 · 30 min read

A cycle in a graph is a path that starts and ends at the same vertex, visiting at least one edge. Detecting cycles is one of the most fundamental graph problems — it appears in deadlock detection, dependency resolution, compiler analysis, and dozens of competitive programming problems. In this post we will cover every major technique: DFS with parent tracking for undirected graphs, the elegant 3-color DFS for directed graphs, Kahn’s algorithm (BFS topological sort), Union-Find, and more. Each method gets a detailed visual walkthrough, an interactive animation, clean C++ code, and a complexity analysis.

Why Cycle Detection Matters

Cycles show up everywhere in computing and real-world modeling:

• Deadlock detection: In operating systems, processes waiting for resources form a “wait-for” graph. A cycle in this directed graph means a deadlock — a set of processes forever waiting on each other.
• Dependency resolution: Package managers (npm, pip, cargo) build dependency graphs. A cycle means circular dependencies — package A needs B which needs A. The build system cannot determine a valid installation order.
• Course prerequisites: Universities model prerequisites as a directed graph. A cycle means an impossible requirement: you need Course A before Course B and Course B before Course A.
• Compiler analysis: Control-flow graphs with cycles represent loops. Detecting back edges (which create cycles) is essential for loop optimisation, dominance computation, and detecting infinite loops.
• Financial fraud: Circular money transfers in transaction graphs can indicate money laundering. Cycle detection helps flag suspicious patterns.
• Garbage collection: Reference-counting garbage collectors cannot reclaim cyclic references. A separate cycle-detection phase (like Python’s gc module) is needed.

Types of Cycles

Cycles in Undirected Graphs

In an undirected graph, a cycle is a path of length ≥ 3 that starts and ends at the same vertex, without repeating any edge. The key subtlety: traversing an edge u—v and immediately going back v—u does not constitute a cycle. That’s why we track the parent node during DFS.

The dashed red edge 4—0 closes the cycle 0→1→2→3→4→0. Without that edge, the graph is a tree (no cycles).

Cycles in Directed Graphs

In a directed graph, a cycle requires that you follow edge directions. Even if nodes u and v are connected by edges u→v and v→w and w→u, the cycle only exists because each edge points in the right direction around the loop.

The directed cycle is A→B→C→A. If we reversed any one edge, the cycle would break.

Self-Loops & Back Edges

A self-loop is a trivial cycle: an edge from a vertex to itself. In DFS terminology, a back edge is an edge that connects a vertex to one of its ancestors in the DFS tree. Every cycle in a graph contains at least one back edge, and every back edge creates a cycle. This is the foundation of DFS-based cycle detection.

Undirected Graph: DFS with Parent Tracking

The simplest cycle detection: run DFS and track each node’s parent. If DFS encounters a visited neighbor that is not the parent of the current node, we’ve found a cycle. Why? In an undirected graph, DFS explores a spanning tree. Any non-tree edge (one connecting to an already-visited, non-parent node) creates a cycle with tree edges.

Visual Walkthrough

Let’s trace DFS on this 6-node undirected graph starting from node 0. The graph has one cycle: 0—1—3—4—2—0.

The algorithm returns true immediately. Node 5 is never explored because we short-circuit on the first cycle found.

Directed Graph: 3-Color DFS

The parent-tracking trick does not work for directed graphs. Consider edges A→B and A→C→B. When DFS from A reaches B via C, it finds B already visited. Is it a cycle? No — B was visited via a different path, not an ancestor. We need a finer-grained approach: the 3-color method.

The Three Colors

The rule is simple: if DFS encounters a GRAY vertex, there is a cycle. A GRAY vertex is on the current path from the DFS root to the current node. An edge to a GRAY vertex is a back edge that closes a cycle. Edges to BLACK vertices are harmless (forward or cross edges).

Visual Walkthrough

Let’s trace the 3-color DFS on this 7-node directed graph. It contains the cycle 1→3→5→1.

The 3-color method correctly identifies the cycle. Note that nodes 2, 4, and 6 were never visited — the algorithm short-circuits on the first back edge. Also note that if we had only used a simple visited[] boolean array (like the undirected method), DFS from node 0 going 0→2→4→6 would mark 6 as visited. Then later, DFS from 0→1→3→5→6 finds 6 visited — but there’s no cycle through 6! The 3 colors prevent this false positive.

Finding the Actual Cycle Path

Detecting that a cycle exists is often not enough — we need to print the cycle. We can reconstruct it using a parent array.

Parent Array Reconstruction

During DFS, maintain a parent[] array: parent[v] = u means we reached v from u. When we find a back edge v→u (where u is GRAY), the cycle is:

For our example, when we find the back edge 5→1:

• gray_ancestor = 1, current_node = 5
• Trace back: parent[5] = 3, parent[3] = 1. So cycle = [1, 3, 5, 1].

For undirected graphs, the same technique works. When DFS at node u finds visited non-parent neighbor v, trace parent pointers from u back to v to reconstruct the cycle.

Cycle Detection via BFS (Kahn’s Algorithm)

Kahn’s Algorithm is a BFS-based approach for topological sorting. Its beautiful side effect: if the topological sort doesn’t include all nodes, the graph has a cycle.

The Idea

Kahn’s algorithm repeatedly removes nodes with in-degree 0 (no incoming edges). In a DAG, this process eventually removes all nodes. If there’s a cycle, the nodes in the cycle always have in-degree ≥ 1 (because of the cycle edges), so they can never be removed.

Quick Example

On our 7-node directed graph (with cycle 1→3→5→1), initial in-degrees are: 0:0, 1:1, 2:1, 3:1, 4:1, 5:1, 6:2. Kahn’s processes: node 0 (in-degree 0), then 2 (becomes 0), then 4 (becomes 0), then 6 (becomes 0). After processing 4 nodes, the queue is empty but count=4 ≠ 7. The remaining nodes {1, 3, 5} form the cycle and can never reach in-degree 0.

Cycle Detection with Union-Find (DSU)

For undirected graphs, the Disjoint Set Union (Union-Find) data structure provides an elegant alternative to DFS. The idea: process edges one by one. For each edge (u, v), check if u and v are already in the same connected component. If yes, adding this edge creates a cycle. If no, union their components.

Walkthrough

Using our 6-node undirected graph (edges: 0-1, 0-2, 1-3, 3-4, 2-4, 3-5):

Interactive Animation: 3-Color DFS

Step through the 3-color DFS cycle detection on a directed graph. Watch nodes transition from WHITE to GRAY to BLACK, and see the back edge that reveals the cycle.

C++ Implementations

Here are clean, competitive-programming-ready implementations of all three major approaches.

1. Undirected Graph — DFS with Parent Tracking

#include <bits/stdc++.h>
using namespace std;

class UndirectedCycle {
    int V;
    vector<vector<int>> adj;

    bool dfs(int u, int parent, vector<bool>& visited) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                if (dfs(v, u, visited))
                    return true;
            } else if (v != parent) {
                return true;  // back edge found
            }
        }
        return false;
    }

public:
    UndirectedCycle(int V) : V(V), adj(V) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bool hasCycle() {
        vector<bool> visited(V, false);
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, -1, visited))
                    return true;
            }
        }
        return false;
    }
};

int main() {
    UndirectedCycle g(6);
    g.addEdge(0, 1); g.addEdge(0, 2);
    g.addEdge(1, 3); g.addEdge(3, 4);
    g.addEdge(2, 4); g.addEdge(3, 5);

    cout << (g.hasCycle() ? "Cycle found" : "No cycle") << endl;
    return 0;
}

2. Directed Graph — 3-Color DFS

#include <bits/stdc++.h>
using namespace std;

class DirectedCycle {
    int V;
    vector<vector<int>> adj;
    enum Color { WHITE, GRAY, BLACK };

    bool dfs(int u, vector<Color>& color, vector<int>& parent,
             int& cycle_start, int& cycle_end) {
        color[u] = GRAY;
        for (int v : adj[u]) {
            if (color[v] == GRAY) {
                cycle_start = v;
                cycle_end = u;
                return true;  // back edge: cycle!
            }
            if (color[v] == WHITE) {
                parent[v] = u;
                if (dfs(v, color, parent, cycle_start, cycle_end))
                    return true;
            }
        }
        color[u] = BLACK;
        return false;
    }

public:
    DirectedCycle(int V) : V(V), adj(V) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    bool hasCycle() {
        vector<Color> color(V, WHITE);
        vector<int> parent(V, -1);
        int cycle_start = -1, cycle_end = -1;

        for (int i = 0; i < V; i++) {
            if (color[i] == WHITE) {
                if (dfs(i, color, parent, cycle_start, cycle_end)) {
                    // Reconstruct and print cycle
                    vector<int> cycle;
                    cycle.push_back(cycle_start);
                    for (int v = cycle_end; v != cycle_start; v = parent[v])
                        cycle.push_back(v);
                    cycle.push_back(cycle_start);
                    reverse(cycle.begin(), cycle.end());

                    cout << "Cycle: ";
                    for (int v : cycle) cout << v << " ";
                    cout << endl;
                    return true;
                }
            }
        }
        return false;
    }
};

int main() {
    DirectedCycle g(7);
    g.addEdge(0, 1); g.addEdge(0, 2);
    g.addEdge(1, 3); g.addEdge(2, 4);
    g.addEdge(3, 5); g.addEdge(4, 6);
    g.addEdge(5, 1); g.addEdge(5, 6);

    if (!g.hasCycle())
        cout << "No cycle" << endl;
    return 0;
}

Output:

Cycle: 1 3 5 1

3. Union-Find (DSU) for Undirected Graphs

#include <bits/stdc++.h>
using namespace std;

class DSU {
    vector<int> parent, rank_;
public:
    DSU(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;  // already same set
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) rank_[rx]++;
        return true;
    }
};

bool hasCycleDSU(int V, vector<pair<int,int>>& edges) {
    DSU dsu(V);
    for (auto& [u, v] : edges) {
        if (!dsu.unite(u, v))
            return true;  // u and v already connected
    }
    return false;
}

int main() {
    int V = 6;
    vector<pair<int,int>> edges = {
        {0,1}, {0,2}, {1,3}, {3,4}, {2,4}, {3,5}
    };

    cout << (hasCycleDSU(V, edges) ? "Cycle found" : "No cycle") << endl;
    return 0;
}

Output:

Cycle found

Complexity Analysis

Time Complexity

Space Complexity

All methods use O(V + E) space for the adjacency list plus O(V) for auxiliary data structures (visited array, color array, parent array, or DSU arrays). The DFS-based methods also use O(V) recursion stack space in the worst case (a chain graph).

Comparison of Methods

Competitive Programming Patterns

Cycle detection appears in many disguises in competitive programming. Here are the most common patterns:

1. Cycles in Permutations

A permutation P of [0..n-1] defines a functional graph: node i has exactly one outgoing edge to P[i]. Every functional graph decomposes into disjoint cycles. To find all cycles, iterate through each node, follow the chain i→P[i]→P[P[i]]→… until you return to the start.

// Count the number of cycles in a permutation
int countCycles(vector<int>& perm) {
    int n = perm.size(), cycles = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            cycles++;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = perm[j];
            }
        }
    }
    return cycles;
}

Key fact: The minimum number of swaps to sort a permutation is n − (number of cycles). This is a classic interview question.

2. Floyd’s Tortoise & Hare (Functional Graphs)

In a functional graph (each node has exactly one outgoing edge, like a linked list that may loop), Floyd’s algorithm detects cycles in O(1) space using two pointers:

• Tortoise moves one step at a time: slow = f(slow)
• Hare moves two steps at a time: fast = f(f(fast))
• If they meet, there is a cycle. Then, reset one pointer to start and advance both at speed 1 to find the cycle’s entry point.

// Floyd's cycle detection in a functional graph
// f(x) returns the single neighbor of x
pair<int,int> floydCycle(int start, function<int(int)> f) {
    int slow = f(start), fast = f(f(start));
    while (slow != fast) {
        slow = f(slow);
        fast = f(f(fast));
    }
    // Find cycle entry
    slow = start;
    while (slow != fast) {
        slow = f(slow);
        fast = f(fast);
    }
    // Find cycle length
    int len = 1;
    int p = f(slow);
    while (p != slow) { p = f(p); len++; }
    return {slow, len};  // {entry_node, cycle_length}
}

This is the technique behind LeetCode’s Linked List Cycle II and Find the Duplicate Number.

3. Negative Cycles (Bellman-Ford)

The Bellman-Ford algorithm detects negative-weight cycles in weighted directed graphs. After V-1 relaxation passes, if any edge can still be relaxed, there exists a negative cycle reachable from the source.

// Returns true if a negative cycle is reachable from source
bool hasNegativeCycle(int V, vector<tuple<int,int,int>>& edges, int src) {
    vector<long long> dist(V, 1e18);
    dist[src] = 0;

    for (int i = 0; i < V - 1; i++)
        for (auto& [u, v, w] : edges)
            if (dist[u] < 1e18 && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;

    // V-th pass: if any edge relaxes, negative cycle exists
    for (auto& [u, v, w] : edges)
        if (dist[u] < 1e18 && dist[u] + w < dist[v])
            return true;
    return false;
}

This is used in currency arbitrage detection, shortest-path problems with negative weights, and problems like SPOJ NEGCYC and Codeforces problems involving Bellman-Ford.

4. Cycle Parity & Bipartiteness

An undirected graph is bipartite if and only if it contains no odd-length cycle. You can check bipartiteness using a 2-coloring BFS/DFS, which is essentially cycle detection with a twist — you’re detecting cycles of odd length.

Practice Problems

Test your understanding with these problems, ordered roughly by difficulty:

Summary

Let’s recap the key takeaways:

1. Undirected graphs: Use DFS with parent tracking or Union-Find. A visited non-parent neighbor means a cycle.
2. Directed graphs: Use the 3-color DFS method. An edge to a GRAY node is a back edge that indicates a cycle. Alternatively, use Kahn’s algorithm — if topological sort can’t process all nodes, there’s a cycle.
3. Cycle reconstruction: Maintain a parent array during DFS. When a back edge is found, trace parent pointers to reconstruct the cycle path.
4. Union-Find is ideal for undirected graphs, especially with online edge insertion (Kruskal’s, incremental connectivity).
5. Floyd’s algorithm detects cycles in functional graphs (each node has out-degree 1) using O(1) extra space.
6. Bellman-Ford detects negative-weight cycles in weighted directed graphs.
7. All DFS/BFS methods run in O(V + E) time. Union-Find runs in O(E · α(V)) ≈ O(E).