Parent Rule
In undirected graphs, an edge back to the immediate parent is not a cycle. We must ignore it during traversal.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
Detect cycles in an undirected graph by tracking parents during DFS. If we encounter a visited node that isn't the current node's parent, a cycle exists.
In undirected graphs, an edge back to the immediate parent is not a cycle. We must ignore it during traversal.
A back-edge connects a node to a previously visited ancestor (other than its parent), forming a closed loop.
Pick a node, start DFS, and pass the current node as the 'parent' to its neighbors. If a neighbor is already visited and not the parent, a cycle is found.
If a graph has no cycles and is connected, it is a Tree. Cycle detection is key to verifying tree structures.