Detect Cycle in Undirected Graph

To detect a cycle in an undirected graph, traverse the graph with DFS or BFS and track each node's parent: if you reach a visited node that is not the parent of the current node, the graph contains a cycle. Union-Find reaches the same answer by merging components edge by edge.

All three approaches run in near-linear time. This lesson defines what a cycle is, implements cycle detection with DFS, BFS, and Union-Find in Python, and compares when each method fits best.

What Is a Cycle in a Graph?

A cycle is a path that starts and ends at the same node without repeating any edge. In an undirected graph, the smallest possible cycle has three nodes, such as A - B - C - A. A graph with no cycles is called acyclic; a connected acyclic graph is a tree.

Going from A to B and straight back along the same edge does not count as a cycle, which is exactly why the algorithms below track each node's parent.

An undirected graph where the path a to b to c back to a forms a cycle on three distinct edges, while going a to b and back reuses one edge and does not count

3 Ways to Detect a Cycle in an Undirected Graph

1) DFS with a Parent Pointer

Depth-first search visits nodes recursively. For each neighbor there are three cases: unvisited (recurse), visited and equal to the parent (ignore, that is the edge we came from), or visited and not the parent (cycle found).

def has_cycle_dfs(graph):
    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False

    return any(node not in visited and dfs(node, None) for node in graph)

cyclic = {"a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b"]}
acyclic = {"a": ["b"], "b": ["a", "c"], "c": ["b"]}
print(has_cycle_dfs(cyclic))   # Outputs: True
print(has_cycle_dfs(acyclic))  # Outputs: False

The any() loop restarts the search from every unvisited node, so disconnected graphs are fully checked.

The three cases of the parent rule: an unvisited neighbor is explored, the parent is ignored, and any other visited neighbor means a cycle

Four DFS snapshots of the same graph showing visited nodes, the current node, parent pointers, and the red back edge from c to a that proves the cycle

2) BFS with a Parent Pointer

Breadth-first search applies the same parent rule with a queue instead of recursion, which avoids recursion-depth limits on large graphs.

from collections import deque

def has_cycle_bfs(graph):
    visited = set()
    for start in graph:
        if start in visited:
            continue
        visited.add(start)
        queue = deque([(start, None)])
        while queue:
            node, parent = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, node))
                elif neighbor != parent:
                    return True
    return False

network = {"r1": ["r2", "r3"], "r2": ["r1", "r4"], "r3": ["r1", "r4"], "r4": ["r2", "r3"]}
print(has_cycle_bfs(network))  # Outputs: True

Three BFS snapshots of the r1 to r4 network where r4 is reached from r2 first and then r3 meets the already visited r4, revealing the cycle

3) Union-Find (Disjoint Set Union)

Union-Find processes edges instead of traversing. Each node starts in its own set, and every edge merges two sets. If an edge connects two nodes already in the same set, that edge closes a cycle.

def has_cycle_union_find(nodes, edges):
    parent = {node: node for node in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in edges:
        root_a, root_b = find(a), find(b)
        if root_a == root_b:
            return True
        parent[root_a] = root_b
    return False

towns = ["p", "q", "r", "s"]
roads = [("p", "q"), ("q", "r"), ("r", "p")]
print(has_cycle_union_find(towns, roads))  # Outputs: True
print(has_cycle_union_find(towns, [("p", "q"), ("r", "s")]))  # Outputs: False

Union-Find growing one set as edges p-q and q-r merge nodes, until edge r-p arrives with both endpoints already inside the same set and closes a cycle

Detect Cycle in Undirected Graph in C++

The same algorithms port directly to C++ with an adjacency list as a vector of vectors. Node d from the diagram is index 3 here, and the triangle 0-1-2 is the cycle.

1) DFS in C++

#include <iostream>
#include <vector>
using namespace std;

bool dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, adj, visited)) return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

int main() {
    vector<vector<int>> adj = {{1, 2}, {0, 2}, {0, 1, 3}, {2}};
    vector<bool> visited(4, false);

    bool cycle = false;
    for (int i = 0; i < 4; i++) {
        if (!visited[i] && dfs(i, -1, adj, visited)) { cycle = true; break; }
    }
    cout << (cycle ? "cycle" : "no cycle");  // Output: cycle
    return 0;
}

2) Union-Find in C++

#include <iostream>
#include <vector>
using namespace std;

int find(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int main() {
    vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 0}};
    vector<int> parent = {0, 1, 2, 3};

    bool cycle = false;
    for (auto [a, b] : edges) {
        int rootA = find(parent, a), rootB = find(parent, b);
        if (rootA == rootB) { cycle = true; break; }
        parent[rootA] = rootB;
    }
    cout << (cycle ? "cycle" : "no cycle");  // Output: cycle
    return 0;
}

Detect Cycle in Undirected Graph in Java

Java uses the same parent rule with an adjacency list of List<List<Integer>>.

1) DFS in Java

import java.util.*;

public class Main {
    static boolean dfs(int node, int parent, List<List<Integer>> adj, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, node, adj, visited)) return true;
            } else if (neighbor != parent) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(
            List.of(1, 2), List.of(0, 2), List.of(0, 1, 3), List.of(2)
        );
        boolean[] visited = new boolean[4];

        boolean cycle = false;
        for (int i = 0; i < 4; i++) {
            if (!visited[i] && dfs(i, -1, adj, visited)) { cycle = true; break; }
        }
        System.out.println(cycle ? "cycle" : "no cycle");  // Output: cycle
    }
}

2) Union-Find in Java

public class Main {
    static int[] parent;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}, {2, 0}};
        parent = new int[]{0, 1, 2, 3};

        boolean cycle = false;
        for (int[] edge : edges) {
            int rootA = find(edge[0]), rootB = find(edge[1]);
            if (rootA == rootB) { cycle = true; break; }
            parent[rootA] = rootB;
        }
        System.out.println(cycle ? "cycle" : "no cycle");  // Output: cycle
    }
}

The Time Complexity of Cycle Detection

DFS and BFS visit each node and edge once, so both run in O(V + E) time and O(V) space, where V is the number of nodes and E the number of edges. Union-Find runs in O(E · α(V)), where α is the inverse Ackermann function, a value that stays below 5 for any practical input, so it behaves like O(E) in practice.

When to Use Each Method

Method	Use it when
DFS with parent	The graph is an adjacency list and recursion depth is safe
BFS with parent	The graph is large or deep enough to overflow recursion
Union-Find	The input is an edge list, or edges arrive one at a time

Union-Find is the standard choice inside Kruskal's minimum spanning tree algorithm, which must reject every edge that would close a cycle.

Examples of Cycle Detection

1) Checking If a Network Has a Redundant Link

In the network graph above, r1 - r2 - r4 - r3 - r1 forms a loop, so has_cycle_bfs() returns True. Removing any one of those links breaks the loop and the function returns False.

2) Validating That a Graph Is a Tree

A connected undirected graph is a tree exactly when it has no cycle, which also means it has exactly V - 1 edges.

def is_tree(graph, edge_count):
    return edge_count == len(graph) - 1

folders = {"root": ["docs", "src"], "docs": ["root"], "src": ["root"]}
print(is_tree(folders, 2))  # Outputs: True

Learn More About Cycle Detection

Cycle Detection in a Directed Graph

The parent trick does not work on directed graphs, because reaching a visited node is normal there. Directed cycle detection tracks the current recursion path (a "grey" state) and reports a cycle only when an edge points back into it.

Finding the Cycle Itself

To return the cycle's nodes rather than a yes/no answer, store each node's parent during the traversal. When the cycle edge appears, walk the parent chain from both endpoints until they meet.

Cycles in Graph Theory

In graph theory terms, a cycle is a closed walk with no repeated edges or nodes except the endpoints. A graph whose every node has degree 2 and which is connected is itself called a cycle graph.

Key Takeaways for Detecting Cycles

The rule - a visited neighbor that is not the current node's parent means a cycle exists.
DFS and BFS - both apply the parent rule in O(V + E) time; BFS avoids recursion limits.
Union-Find - an edge joining two nodes already in the same set closes a cycle; ideal for edge lists.
Disconnected graphs - restart the search from every unvisited node or the check is incomplete.
Directed graphs - need a different method (recursion-path tracking), not the parent rule.

Both traversals here build on the same queue-based search pattern. Read our lesson on breadth first search in Python for the traversal itself in more depth.

The Top 10 favtutor Features You Might Have Overlooked

Detect Cycle in Undirected Graph (DFS, BFS, Union-Find)