Cycle detection in graphs in Data Structures Theory - Mini Project: Build & Apply

Cycle Detection in Graphs

📖 Scenario: You are working with a simple network of connected points called a graph. Sometimes, these connections form loops, called cycles. Detecting these cycles is important in many real-world situations, like checking if a road map has circular routes or if a task list has circular dependencies.

🎯 Goal: Build a step-by-step understanding of how to detect cycles in an undirected graph using a simple data structure and logic.

📋 What You'll Learn

Create a graph using an adjacency list representation

Set up a helper structure to track visited nodes

Implement a function to detect cycles using depth-first search

Complete the cycle detection by checking all nodes

💡 Why This Matters

🌍 Real World

Cycle detection helps in network routing, task scheduling, and detecting infinite loops in workflows.

💼 Career

Understanding cycle detection is important for software developers, data scientists, and network engineers to ensure data integrity and system reliability.

1

Create the graph as an adjacency list

Create a dictionary called graph representing an undirected graph with these exact edges: 1 connected to 2 and 3, 2 connected to 1 and 4, 3 connected to 1 and 4, 4 connected to 2 and 3.

Data Structures Theory

# Create the graph dictionary with the specified edges
# Your code here

Hint

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

2

Set up a visited dictionary

Create a dictionary called visited with keys 1, 2, 3, and 4, all set to False to track if a node has been checked.

Data Structures Theory

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
# Create the visited dictionary with all nodes set to False
# Your code here

Hint

Use a dictionary with the same keys as the graph nodes and set all values to False.

3

Write the cycle detection function

Define a function called has_cycle that takes node, parent, graph, and visited as parameters. Use depth-first search to mark node as visited. For each neighbor in graph[node], if the neighbor is not visited, recursively call has_cycle with neighbor and node. If a neighbor is visited and is not the parent, return True. Return False if no cycle is found.

Data Structures Theory

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
visited = {1: False, 2: False, 3: False, 4: False}
# Define the has_cycle function using DFS
# Your code here

Hint

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

4

Check all nodes for cycles

Use a for loop to go through each node in graph. If visited[node] is False, call has_cycle(node, -1, graph, visited). This completes the cycle detection setup.

Data Structures Theory

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
visited = {1: False, 2: False, 3: False, 4: False}

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

# Check all nodes for cycles
# Your code here

Hint

Loop through all nodes and call the cycle detection function on unvisited nodes.

Practice

1. What is the main purpose of cycle detection in a graph?

easy

A. To count the number of nodes

B. To find if there is a loop in the graph

C. To sort the nodes in ascending order

D. To find the shortest path between nodes

Solution

1. Step 1: Understand the concept of cycle detection

   Cycle detection checks if a graph contains any loops where you can start at a node and return to it by following edges.

2. Step 2: Identify the main goal

   The main goal is to find if such loops exist, which can cause problems like infinite loops in algorithms.

3. Final Answer:

   To find if there is a loop in the graph -> Option B

4. Quick Check:

   Cycle detection = find loops [OK]

Hint: Cycle detection means finding loops in graphs [OK]

Common Mistakes:

• Confusing cycle detection with sorting
• Thinking it counts nodes instead of finding loops
• Assuming it finds shortest paths

2. Which data structure is commonly used to detect cycles in a directed graph using DFS?

easy

A. Queue

B. Stack

C. Hash Set to track recursion stack

D. Priority Queue

Solution

1. Step 1: Recall DFS cycle detection method

   DFS explores nodes deeply and uses a recursion stack to track nodes currently in the path.

2. Step 2: Identify the data structure used

   A hash set or boolean array is used to track nodes in the recursion stack to detect back edges indicating cycles.

3. Final Answer:

   Hash Set to track recursion stack -> Option C

4. Quick Check:

   DFS cycle detection uses recursion stack tracking [OK]

Hint: Use a hash set to track nodes in current DFS path [OK]

Common Mistakes:

• Using queue instead of stack for DFS
• Not tracking recursion stack nodes
• Confusing with BFS cycle detection

3. Consider the directed graph edges: [(1, 2), (2, 3), (3, 4), (4, 2)]. Does this graph contain a cycle?

medium

A. Yes, there is a cycle involving nodes 2, 3, and 4

B. Yes, but only between nodes 1 and 2

C. No, it is acyclic

D. No, because node 1 has no incoming edges

Solution

1. Step 1: Trace the edges to find cycles

   Edges form path 1->2->3->4 and then 4->2, which loops back to node 2.

2. Step 2: Identify the cycle nodes

   The cycle is formed by nodes 2, 3, and 4 because you can go from 2 to 3 to 4 and back to 2.

3. Final Answer:

   Yes, there is a cycle involving nodes 2, 3, and 4 -> Option A

4. Quick Check:

   Edges 4->2 create cycle 2-3-4 [OK]

Hint: Look for edges that point back to earlier nodes [OK]

Common Mistakes:

• Ignoring the edge 4->2 that closes the cycle
• Thinking node 1's edges affect cycle
• Assuming no cycle if start node has no incoming edges

4. Given this DFS-based cycle detection pseudocode, what is the error?

function dfs(node):
  visited[node] = true
  for neighbor in graph[node]:
    if visited[neighbor]:
      return true
    if dfs(neighbor):
      return true
  return false

medium

A. It does not track nodes in the current recursion stack

B. It marks nodes as visited too late

C. It should use a queue instead of recursion

D. It returns false too early

Solution

1. Step 1: Analyze the visited marking

   The code marks nodes as visited but does not distinguish between nodes visited in current path and fully processed nodes.

2. Step 2: Identify missing recursion stack tracking

   Without tracking nodes in the current recursion stack, it cannot detect back edges properly, causing false negatives.

3. Final Answer:

   It does not track nodes in the current recursion stack -> Option A

4. Quick Check:

   Missing recursion stack tracking causes wrong cycle detection [OK]

Hint: Track recursion stack separately to detect cycles [OK]

Common Mistakes:

• Using only visited array without recursion stack
• Confusing visited with recursion stack
• Thinking recursion depth causes error

5. You have a task scheduling system represented as a directed graph where edges mean "task A must finish before task B starts." How can cycle detection help in this system?

hard

A. It counts the total number of tasks

B. It finds tasks that can run in parallel

C. It sorts tasks by their duration

D. It detects impossible schedules due to circular dependencies

Solution

1. Step 1: Understand task scheduling graph meaning

   Edges show dependencies; a cycle means tasks depend on each other in a loop.

2. Step 2: Identify the role of cycle detection

   If a cycle exists, the schedule is impossible because tasks wait on each other endlessly.

3. Final Answer:

   It detects impossible schedules due to circular dependencies -> Option D

4. Quick Check:

   Cycle detection finds circular dependencies [OK]

Hint: Cycles mean tasks depend on each other endlessly [OK]

Common Mistakes:

• Thinking cycle detection sorts tasks
• Assuming cycles allow parallel tasks
• Confusing cycle detection with counting tasks