Cycle Detection in Undirected Graph in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a cycle in an undirected graph?

A cycle is a path that starts and ends at the same vertex with at least one edge, and no vertex is repeated except the starting/ending vertex.

beginner

Which data structure is commonly used to detect cycles in an undirected graph?

Depth-First Search (DFS) is commonly used to detect cycles by checking if a visited node is encountered again and is not the parent of the current node.

intermediate

In cycle detection using DFS, why do we keep track of the parent node?

To avoid falsely detecting a cycle when revisiting the immediate parent node, since the parent is connected by the edge we came from.

intermediate

What is the time complexity of cycle detection in an undirected graph using DFS?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and edge is visited once.

advanced

How does the Union-Find (Disjoint Set) data structure help in cycle detection?

Union-Find helps detect cycles by grouping connected vertices. If two vertices of an edge belong to the same group, adding that edge creates a cycle.

What indicates a cycle during DFS in an undirected graph?

A Visiting a node with no edges

B Visiting a node that is already visited and is not the parent

C Visiting the parent node again

D Visiting a node for the first time

A cycle is detected if we visit a node that is already visited and is not the parent of the current node.

Which of these is NOT a valid method for cycle detection in an undirected graph?

A Depth-First Search (DFS)

B Breadth-First Search (BFS) with parent tracking

C Union-Find (Disjoint Set)

D Topological Sort

Topological Sort is used for cycle detection in directed graphs, not undirected graphs.

What is the role of the 'parent' parameter in DFS cycle detection?

A To avoid counting the edge back to the immediate predecessor as a cycle

B To mark the starting node

C To store the depth of the node

D To count the number of edges

The parent parameter helps avoid false cycle detection by ignoring the edge back to the immediate predecessor.

If Union-Find finds two vertices of an edge in the same set, what does it mean?

A A cycle is detected

B The graph is disconnected

C The edge is a bridge

D The graph is a tree

If both vertices are in the same set, adding the edge creates a cycle.

What is the initial step in cycle detection using DFS?

A Mark all nodes as visited

B Add all edges to a queue

C Start DFS from any unvisited node

D Initialize Union-Find sets

DFS starts from any unvisited node to explore the graph and detect cycles.

Explain how DFS can be used to detect a cycle in an undirected graph.

Think about revisiting nodes and the role of the parent.

Describe how the Union-Find data structure detects cycles in an undirected graph.

Focus on grouping connected vertices and checking for repeated connections.

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