Cycle Detection

DSA · Graphs

Theory

In an undirected graph a cycle exists if DFS reaches an already-visited vertex that is not the parent it came from. In a directed graph, DFS tracks three states: unvisited, on the current path, and finished; reaching a vertex that is still on the current path means a cycle. Union-find can also detect cycles in undirected graphs by checking whether an edge joins two vertices already in the same set.

Why we use it

Cycles break dependency ordering (circular imports, deadlocks) and must be detected before scheduling tasks.

When to use it

Use it to validate task or course prerequisites, detect deadlocks, check that a graph is a tree, and in build systems.

How it works

  1. DFS with states: unvisited, visiting, done
  2. Mark u as visiting
  3. For each neighbour v
  4. v is visiting? Yes: Cycle found. No: If unvisited, DFS(v).
  5. Mark u done; no cycle if DFS finishes

Syntax

Directed (three colours):
state[v] = 1 (on path)
for nb in graph[v]:
    if state[nb] == 1: cycle!
    if state[nb] == 0: dfs(nb)
state[v] = 2 (done)

Example

def has_cycle(graph):
    state = {v: 0 for v in graph}      # 0 new, 1 on path, 2 done
    def dfs(v):
        state[v] = 1
        for nb in graph[v]:
            if state[nb] == 1:
                return True
            if state[nb] == 0 and dfs(nb):
                return True
        state[v] = 2
        return False
    for v in graph:
        if state[v] == 0 and dfs(v):
            return True
    return False

courses_ok = {"SQL": ["Python"], "Python": ["Spark"], "Spark": []}
courses_bad = {"A": ["B"], "B": ["C"], "C": ["A"]}
print("Valid plan has cycle:", has_cycle(courses_ok))
print("Circular plan has cycle:", has_cycle(courses_bad))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic