G-12. Detect a Cycle in an Undirected Graph using DFS | C++ | Java

Detecting a cycle in an undirected graph using DFS

Main idea

• Use depth-first search (DFS) to determine whether any simple cycle exists in an undirected graph.
• During DFS, pass the parent node so that encountering the parent as a visited neighbor is not treated as a cycle.
• If you encounter an adjacent node that is already visited and is not the parent, a cycle exists.
• For graphs with multiple connected components, run DFS from every unvisited node.

Detailed algorithm (pseudocode-style)

1. Data structures

   • visited[]: boolean array initialized to false for all nodes.
   • adjacency list representation of the graph.
   • DFS function signature: dfs(node, parent)

2. DFS function (returns boolean: true if a cycle is found in this call/subtree)

   • visited[node] = true
   • For each neighbor v in adjacency[node]:
     • If visited[v] == false:
       • If dfs(v, node) returns true, immediately return true
     • Else (visited[v] == true):
       • If v != parent, then return true (visited non-parent neighbor ⇒ cycle)
   • After exploring all neighbors, return false (no cycle found from this node)

3. Main driver (handles multiple components)

   • For every node i in 1..N (or 0..N-1 for 0-based indexing):
     • If visited[i] == false:
       • If dfs(i, -1) returns true, then there exists a cycle (stop and report)
   • If none of the DFS calls returned true, report no cycle

Key check: if a visited neighbor is not the parent, that indicates a cycle.

Example traversal (illustrative)

• Start DFS at node 1: mark visited, explore neighbors (2 then 3).
• Example chain explored: 1 → 2 → 5 → 7 → 6 → 3 → 4.
• If DFS reaches a node whose neighbor is already visited and is not its parent (for example encountering node 1 from a node that is not its parent), that is detected as a cycle.
• When any DFS call returns true, propagate that true back up the recursion stack to the driver and conclude the graph has a cycle.

Key implementation details / reminders

• Always pass a parent argument in DFS to ignore the immediate back-edge to the parent.
• Initialize visited[] to false before starting; use -1 (or null) as the parent for initial calls.
• For graphs with multiple components, iterate over all nodes and call DFS for unvisited nodes.
• Use an adjacency list representation for the graph input.

Complexity

• Time: O(V + E) — every vertex and every edge is processed a constant number of times during DFS.
• Space: O(V) for visited[] plus recursion stack, which is O(V) in the worst case (so overall O(V) auxiliary space).

Coding notes

• Example implementations are commonly shown in C++ and Java.
• Dry-run the algorithm on multiple graphs to reinforce understanding and recursion concepts.

References mentioned

• Previous video: cycle detection using BFS.
• Lectures: lecture 2/3 (adjacency list), lecture 4 (connected components).
• Recursion playlist (for recursion fundamentals).
• Other playlists referenced: dynamic programming and system design/study.

Speakers / sources

• Presenter / channel host (unnamed in subtitles).
• The video references its own prior videos and lecture series and shows code in C++ and Java.
• Background music is played at the end of the video.