How do you detect a cycle in an Undirected Graph?

Difficulty: 5/10

graph traversal, union-find, DFS

Undirected Graph Cycle Detection

In an undirected graph, DFS can detect a cycle by tracking the parent of each vertex. When visiting a neighbor that is already visited and is not the current vertex's parent, a cycle exists. Another approach is Union-Find: if an edge connects two vertices already in the same set, that edge creates a cycle.

javascript

1
DFS uses a parent check.
2
Union-Find works particularly well when processing an edge list.
3
DFS complexity: O(V+E).
4
Union-Find is approximately O(E alpha(V)) with path compression and union by rank.

Scenario Questions

0-2 years experience

2-5 years experience

Follow-up Questions