Cycle Detection in Undirected Graph in DSA Python

Mental Model

We want to find if a path loops back to a node already visited, showing a cycle.

Analogy: Imagine walking paths in a park. If you return to a spot you already visited without retracing your last step, you found a loop.

0 -> 1 -> 2
↑         ↓
4 ← 3 ← 5

Each arrow is a path connecting places (nodes).

Dry Run Walkthrough

Input: Graph edges: (0-1), (1-2), (2-0), (1-3), (3-4)

Goal: Detect if there is any cycle in the graph.

Step 1: Start DFS from node 0, mark 0 visited

Visited: {0}
Stack: [0]

Why: We begin exploring from node 0 to find cycles.

Step 2: Move to neighbor 1, mark 1 visited, parent of 1 is 0

Visited: {0,1}
Stack: [0,1]

Why: Explore neighbors to find back edges indicating cycles.

Step 3: Move to neighbor 2, mark 2 visited, parent of 2 is 1

Visited: {0,1,2}
Stack: [0,1,2]

Why: Continue deeper to check for cycles.

Step 4: Check neighbors of 2: 0 is visited and not parent, cycle found

Cycle detected via edge 2 -> 0

Why: Visiting a visited node that is not parent means a cycle.

Result:

Cycle detected in the graph.

Annotated Code

DSA Python

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def _dfs(self, v, visited, parent):
        visited[v] = True
        for neighbor in self.graph[v]:
            if not visited[neighbor]:
                if self._dfs(neighbor, visited, v):
                    return True
            elif neighbor != parent:
                return True
        return False

    def has_cycle(self):
        visited = [False] * self.V
        for i in range(self.V):
            if not visited[i]:
                if self._dfs(i, visited, -1):
                    return True
        return False

# Driver code
if __name__ == '__main__':
    g = Graph(5)
    g.add_edge(0, 1)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(1, 3)
    g.add_edge(3, 4)

    if g.has_cycle():
        print("Cycle detected in the graph.")
    else:
        print("No cycle found in the graph.")

visited[v] = True

Mark current node as visited to avoid revisiting.

for neighbor in self.graph[v]:

Check all neighbors of current node.

if not visited[neighbor]:

If neighbor not visited, explore it recursively.

if self._dfs(neighbor, visited, v):

If cycle found deeper, propagate True up.

elif neighbor != parent:

If neighbor visited and not parent, cycle detected.

for i in range(self.V):

Check all nodes to cover disconnected parts.

if not visited[i]:

Start DFS from unvisited node.

if self._dfs(i, visited, -1):

If cycle found from this node, return True.

Output

Cycle detected in the graph.

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V) for the visited array and recursion stack in worst case

vs Alternative: Compared to checking all paths naively, DFS cycle detection is efficient and avoids repeated work.

Edge Cases

Empty graph with no edges

No cycle detected as there are no edges

DSA Python

for i in range(self.V):

Graph with single node and no edges

No cycle detected since no edges exist

DSA Python

for i in range(self.V):

Disconnected graph with multiple components

Cycle detection runs on each component separately

DSA Python

if not visited[i]:

When to Use This Pattern

When you see a problem asking if an undirected graph contains loops, use DFS with parent tracking to detect cycles efficiently.

Common Mistakes

Mistake: Treating visited neighbor as cycle without checking if it is the parent
Fix: Add condition to ignore the edge back to parent node during DFS.

Summary

Detects if an undirected graph contains any cycle using DFS.

Use when you need to find loops in undirected graphs efficiently.

The key is to track the parent node to distinguish back edges from valid tree edges.

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