Questions
14 of 59
How do you detect a cycle in an Undirected Graph?
Difficulty: 3/10
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.
Follow-up Questions
- Why do we ignore the parent edge in DFS?
- How does Union-Find detect a cycle?