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.

How to spot this pattern

In an undirected graph every edge is stored twice, so the node you just came from will always look like a revisit. Passing the parent down and excusing exactly that one neighbour is the whole technique — any other already-seen neighbour is a genuine back edge, and therefore a cycle.

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

▶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

Common pitfalls

Treating any visited neighbour as a cycle

✗ Wrong

for u in adj[v]:
    if seen[u]: return True

✓ Right

elif u != parent:
    return True

The edge you arrived on is bidirectional, so the parent is always already visited — this reports a cycle on a two-node graph with a single edge. The parent must be excluded from the back-edge test.

Discarding the recursive result

✗ Wrong

if not seen[u]:
    dfs(u, v)

✓ Right

if not seen[u]:
    if dfs(u, v): return True

A cycle found deeper in the recursion never reaches the caller, so the function reports False for graphs that clearly contain one. Recursive answers have to be propagated up.

Checking only the component containing node 0

✗ Wrong

return dfs(0, -1)

✓ Right

for s in range(n):
    if not seen[s] and dfs(s, -1): return True

The cycle may live in a component unreachable from node 0. Every unvisited vertex needs to seed its own search, with -1 standing in for "no parent".

06

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.

07

Complexity

Time

O(V + E)

Space

O(V)

Recursion depth up to V.