Cycle Detection (Undirected Graph)
Algorithm for detecting cycles in an undirected graph using DFS with a parent parameter.
⟳ Undirected Cycle Detective
Cycles in Undirected Graphs
Understanding cycles when edges have no direction.
Undirected Graph (No Cycle = Tree)
In an undirected graph, edges have no direction — if A connects to B, then B also connects to A. A graph with no cycles is called a tree (or forest if disconnected). In a tree, there's exactly one path between any two nodes.
A — B — C: each edge goes both ways. No loops — this is a tree.
Undirected Graph (With Cycle)
A cycle in an undirected graph means you can start at a node, follow edges, and return to the starting node without reusing any edge. The key difference from directed graphs: we must ignore the edge we came from (the parent edge) since it trivially leads back.
A — B — C — A: following edges forms a loop — that's a cycle!
The Parent Trick
In undirected graphs, every edge appears twice in the adjacency list. When DFS goes from A to B, B's neighbor list includes A. But going back to A isn't a cycle — it's just the same edge in reverse! We use a parent parameter to remember where we came from and skip that edge.
A cycle is detected when we find a visited neighbor that is NOT our parent. This means there's a different path leading back to that node — a true cycle!