Cycle Detection in Undirected Graph in DSA Python - Execution Trace

Concept Flow - Cycle Detection in Undirected Graph

Start at any node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS

↓

If cycle found

↓

Return True

↓

If all neighbors checked

↓

Return False

Start DFS from any node, mark visited, check neighbors. If a visited neighbor is not the parent, cycle exists.

Execution Sample

DSA Python

def dfs(node, parent):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if dfs(neighbor, node):
                return True
        elif neighbor != parent:
            return True
    return False

DFS visits nodes, checks if a visited neighbor is not parent to detect cycle.

Execution Table

Step	Operation	Current Node	Visited Set	Stack (Call Path)	Cycle Detected	Visual State
1	Start DFS at node 0	0	{}	[0]	No	0
2	Visit neighbor 1 of 0	1	{0}	[0,1]	No	0 - 1
3	Visit neighbor 2 of 1	2	{0,1}	[0,1,2]	No	0 - 1 - 2
4	Visit neighbor 0 of 2	0	{0,1,2}	[0,1,2]	Yes (neighbor visited and not parent)	Cycle found: 0 - 1 - 2 - 0
5	Return True up call stack	2	{0,1,2}	[0,1]	Yes	Cycle confirmed
6	Return True up call stack	1	{0,1,2}	[0]	Yes	Cycle confirmed
7	Return True up call stack	0	{0,1,2}	[]	Yes	Cycle confirmed
8	Stop DFS as cycle detected	-	{0,1,2}	[]	Yes	Final graph state with cycle

💡 Cycle detected when visiting node 0 again from node 2 which is not parent

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
visited	{}	{0}	{0,1}	{0,1,2}	{0,1,2}	{0,1,2}	{0,1,2}	{0,1,2}
stack	[]	[0]	[0,1]	[0,1,2]	[0,1,2]	[0,1]	[0]	[]
cycle_detected	No	No	No	No	Yes	Yes	Yes	Yes

Key Moments - 3 Insights

Why do we check if the visited neighbor is not the parent?

Because in an undirected graph, the edge back to the parent is normal and not a cycle. The cycle is detected only if a visited neighbor is different from the parent (see Step 4 in execution_table).

What happens if the graph is disconnected?

We run DFS from each unvisited node until all nodes are visited or a cycle is found. The example shows one connected component only.

Why do we return True immediately when a cycle is found?

To stop further unnecessary traversal since one cycle is enough to confirm the graph has a cycle (see Steps 4-7 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the visited set after Step 3?

A {0,1,2}

B {0,1}

C {0}

D {}

💡 Hint

Check the 'Visited Set' column at Step 3 in execution_table.

At which step does the cycle get detected?

A Step 2

B Step 4

C Step 6

D Step 8

💡 Hint

Look for 'Cycle Detected' column showing 'Yes' first time in execution_table.

If the graph had no cycle, what would be the final value of 'cycle_detected' in variable_tracker?

A Yes

B No

C Depends on start node

D Undefined

💡 Hint

Cycle detection returns True only if a cycle is found; otherwise, it remains No as per variable_tracker.

Concept Snapshot

Cycle Detection in Undirected Graph using DFS:
- Start DFS from any node
- Mark node visited
- For each neighbor:
  - If not visited, recurse DFS
  - If visited and not parent, cycle found
- Return True if cycle detected, else False
- Stops early on cycle detection

Full Transcript

Cycle detection in an undirected graph uses depth-first search (DFS). We start from any node and mark it visited. For each neighbor, if it is not visited, we recursively call DFS. If the neighbor is visited and is not the parent node, it means a cycle exists. We return True immediately to stop further search. The visited set grows as nodes are explored. The stack tracks the current path. When a cycle is found, the function returns True up the call stack. If no cycle is found after exploring all nodes, the function returns False. This method works even if the graph is disconnected by running DFS from each unvisited node.

Practice

1. What does cycle detection in an undirected graph help us find?

easy

A. The shortest path between two vertices

B. Whether there is a path that starts and ends at the same vertex without repeating edges

C. The total number of vertices in the graph

D. The maximum degree of any vertex

Solution

1. Step 1: Understand cycle meaning in undirected graph

   A cycle is a path that starts and ends at the same vertex without repeating edges or vertices (except start/end).

2. Step 2: Identify what cycle detection checks

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same vertex without repeating edges -> Option B

4. Quick Check:

   Cycle detection = find loops [OK]

Hint: Cycle means a closed loop path in graph [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Thinking cycle counts vertices only
• Mixing cycle with vertex degree

2. Which Python data structure is commonly used to keep track of visited nodes during cycle detection in an undirected graph?

easy

A. Set

B. List

C. Dictionary

D. Tuple

Solution

1. Step 1: Identify purpose of visited tracking

   We need to quickly check if a node was visited before to avoid revisiting and detect cycles.

2. Step 2: Choose data structure with fast membership check

   Set provides O(1) average time for membership checks, making it ideal for visited nodes.

3. Final Answer:

   Set -> Option A

4. Quick Check:

   Visited nodes stored in set [OK]

Hint: Use set for fast visited checks [OK]

Common Mistakes:

• Using list causes slow membership checks
• Using tuple which is immutable and not suitable
• Using dictionary unnecessarily when set suffices

3. What will be the output of the following code snippet detecting cycle in an undirected graph?

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
visited = set()
def dfs(node, parent):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if dfs(neighbor, node):
                return True
        elif neighbor != parent:
            return True
    return False

print(dfs(0, -1))

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Analyze graph structure

   The graph has 3 nodes connected in a triangle: 0-1, 1-2, 2-0, which forms a cycle.

2. Step 2: Trace DFS cycle detection

   Starting at node 0, DFS visits 1, then 2. When 2 checks neighbors, it finds 0 visited and not parent, so returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Triangle graph has cycle = True [OK]

Hint: Triangle graph always has cycle [OK]

Common Mistakes:

• Ignoring parent check causes false positives
• Assuming no cycle in small graphs
• Confusing return values in DFS

4. Find the bug in this cycle detection code for an undirected graph:

def dfs(node, parent, graph, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, node, graph, visited)
        elif neighbor != parent:
            return True
    return False

medium

A. Graph should be directed

B. Visited set is not initialized

C. Parent parameter is not used

D. Missing return statement in recursive dfs call

Solution

1. Step 1: Check recursive call return usage

   The recursive call dfs(neighbor, node, graph, visited) is made but its return value is ignored.

2. Step 2: Understand impact on cycle detection

   If a cycle is found deeper in recursion, it won't propagate True back up, so function may miss cycles.

3. Final Answer:

   Missing return statement in recursive dfs call -> Option D

4. Quick Check:

   Return recursive call result to detect cycles [OK]

Hint: Always return recursive DFS results [OK]

Common Mistakes:

• Ignoring return value of recursive calls
• Not passing visited set properly
• Confusing parent usage

5. Given an undirected graph represented as adjacency list:

graph = {
  0: [1],
  1: [0, 2],
  2: [1, 3],
  3: [2, 4, 5],
  4: [3, 5],
  5: [3, 4]
}

Which nodes form a cycle in this graph?

hard

A. No cycles in this graph

B. Nodes 0, 1, 2 form a cycle

C. Nodes 3, 4, 5 form a cycle

D. All nodes form a cycle

Solution

1. Step 1: Analyze adjacency list for cycles

   Nodes 3, 4, and 5 connect in a triangle: 3-4, 4-5, 5-3, forming a cycle.

2. Step 2: Check other nodes for cycles

   Nodes 0, 1, 2 form a simple chain without loops, so no cycle there.

3. Final Answer:

   Nodes 3, 4, 5 form a cycle -> Option C

4. Quick Check:

   Triangle subgraph = cycle [OK]

Hint: Look for triangle connections to find cycles [OK]

Common Mistakes:

• Assuming chain is a cycle
• Ignoring cycle in subgraph
• Thinking all nodes must form cycle