Cycle Detection in Undirected Graph in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS in an undirected graph

What is the output of the following code that detects a cycle in an undirected graph using DFS?

DSA Python

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

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2, 4], 4: [3]}
visited = {k: False for k in graph}

has_cycle = False
for node in graph:
    if not visited[node]:
        if dfs(node, -1, graph, visited):
            has_cycle = True
            break
print(has_cycle)

A True

B False

C KeyError

D TypeError

💡 Hint

Think about whether the graph contains a triangle or loop.

The graph contains a cycle formed by nodes 0, 1, and 2. The DFS detects this cycle and returns True.

❓ Predict Output

intermediate

Output of cycle detection using BFS in an undirected graph

What is the output of the following code that detects a cycle in an undirected graph using BFS?

DSA Python

from collections import deque

def bfs(start, graph, visited):
    queue = deque([(start, -1)])
    visited[start] = True
    while queue:
        node, parent = queue.popleft()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append((neighbor, node))
            elif neighbor != parent:
                return True
    return False

graph = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3]}
visited = {k: False for k in graph}

has_cycle = False
for node in graph:
    if not visited[node]:
        if bfs(node, graph, visited):
            has_cycle = True
            break
print(has_cycle)

A False

B True

C IndexError

D NameError

💡 Hint

Check if the graph has any loops or back edges.

The graph is a simple chain with no cycles, so the BFS returns False.

🔧 Debug

advanced

Identify the error in cycle detection code

What error does the following code produce when detecting cycles in an undirected graph?

DSA Python

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

graph = {0: [1], 1: [0, 2], 2: [1]}
visited = {k: False for k in graph}

has_cycle = False
for node in graph:
    if not visited[node]:
        if dfs(node, -1, graph, visited):
            has_cycle = True
            break
print(has_cycle)

A The code prints False

B The code raises a RecursionError

C The code raises a KeyError

D The code prints True

💡 Hint

Look carefully at the condition that detects a cycle.

The code incorrectly treats the edge to the parent as a cycle, so it returns True even though no cycle exists.

🚀 Application

advanced

Number of connected components with cycles

Given the graph below, how many connected components contain at least one cycle?

DSA Python

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

# Use DFS or BFS to find connected components and detect cycles in each.

A 0

B 2

C 1

D 3

💡 Hint

Check each connected component for cycles separately.

Only the component with nodes 0,1,2,3 contains a cycle (triangle 1-2-3). The others are simple chains.

🧠 Conceptual

expert

Why does cycle detection in undirected graphs require parent tracking?

Why is it necessary to track the parent node when detecting cycles in an undirected graph using DFS or BFS?

A To improve the speed of traversal by skipping visited nodes

B To avoid falsely detecting the immediate edge back to the parent as a cycle

C To store the path for printing the cycle nodes later

D To prevent visiting nodes with higher values first

💡 Hint

Think about the difference between a back edge and the edge to the parent.

In undirected graphs, the edge to the parent is always present and should not be counted as a cycle. Tracking the parent helps distinguish this from actual cycles.

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