Cycle Detection in Undirected Graph in DSA Python - Build from Scratch

Cycle Detection in Undirected Graph

📖 Scenario: You are working on a network system where devices are connected by cables. You want to check if there is any loop (cycle) in the network connections because loops can cause problems like data packets circulating endlessly.

🎯 Goal: Build a program to detect if an undirected graph (network) contains any cycle using depth-first search (DFS).

📋 What You'll Learn

Create a graph as a dictionary where keys are node names and values are lists of connected nodes.

Create a helper set to keep track of visited nodes.

Write a DFS function that checks for cycles by tracking the parent node.

Print True if a cycle is found, otherwise False.

💡 Why This Matters

🌍 Real World

Network engineers use cycle detection to prevent loops in network topologies that can cause broadcast storms and network failures.

💼 Career

Understanding graph traversal and cycle detection is important for roles in software development, network engineering, and data analysis where graph data structures are common.

1

Create the graph data structure

Create a dictionary called graph with these exact connections: 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C'], 'E': []

DSA Python

# Create the graph dictionary with the given connections
# Your code here

Hint

Use a dictionary where each key is a node and the value is a list of connected nodes.

2

Create a set to track visited nodes

Create an empty set called visited to keep track of nodes that have been checked

DSA Python

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
    'E': []
}

# Create an empty set called visited
# Your code here

Hint

Use set() to create an empty set for visited nodes.

3

Write the DFS function to detect cycles

Define a function called dfs that takes parameters node and parent. Inside, add node to visited. For each neighbor in graph[node], if neighbor is not in visited, recursively call dfs(neighbor, node). If neighbor is visited and not equal to parent, return True. Return False if no cycle is found.

DSA Python

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
    'E': []
}

visited = set()

# Define dfs(node, parent) function to detect cycles
# Your code here

Hint

Use recursion to explore neighbors and check if a visited neighbor is not the parent to detect a cycle.

4

Check all nodes and print if cycle exists

Use a for loop with variable node to iterate over graph. If node is not in visited, call dfs(node, None). If dfs returns True, print True and break the loop. If no cycle is found after the loop, print False.

DSA Python

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
    'E': []
}

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

# Use a for loop to check each node and print True if cycle found, else False
# Your code here

Hint

Loop through all nodes to ensure disconnected parts are checked. Use else on the loop to print False if no cycle is found.

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