GeeksforGeeks Medium

Detect Cycle in Undirected Graph (DFS)

Does an undirected graph contain a cycle? Detect it with DFS.

graphdfscycle

02

Intuition

💡

Identical rule to the BFS version — an already-visited neighbour that is not the parent closes a loop — but the parent travels down the recursion instead of inside a queue. Such an edge is called a back edge, and in an undirected graph a back edge and a cycle are the same thing.

03

Approach

1

Pass the parent down

dfs(v, parent): mark v, then for each neighbour u either recurse (if unvisited) or check whether u != parent.

2

Back edge = cycle

A visited, non-parent neighbour is an edge back into the part of the graph already on the path — the definition of a cycle here.

3

Why directed graphs need more

In a directed graph an edge into a finished vertex is harmless, so the parent trick fails; that variant needs the grey/black recursion-stack check instead.

04

Solution & live demo

python

▶1def has_cycle_undirected_dfs(n, adj):
▶2    seen = [False] * n
▶3    def dfs(v, parent):
▶4        seen[v] = True
▶5        for u in adj[v]:
▶6            if not seen[u]:
▶7                if dfs(u, v): return True
▶8            elif u != parent:     # back edge
▶9                return True
▶10        return False
▶11    for s in range(n):            # every component
▶12        if not seen[s] and dfs(s, -1):
▶13            return True
▶14    return False

05

Edge cases

Tree

Every visited neighbour is the parent — returns false.

Self-loop v–v

u == v is visited and not the parent — correctly a cycle.

Disconnected graph

Outer loop covers every component.

06

Complexity

Time

O(V + E)

Space

O(V)

Recursion depth up to V.