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

Need a 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

Need a 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

Need a 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

Need a hint?

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