juniorGraph Theory

What is a Cycle in a graph?

Updated Apr 28, 2026

Short answer

A cycle in a graph is a path that starts and ends at the same vertex while following a sequence of connected edges, with no repeated vertices or edges except the starting and ending vertex. Cycles represent circular relationships where you can return to the point where you began. Detecting cycles is an important graph problem used in areas like dependency checking, scheduling, and network analysis.

Deep explanation

A cycle exists when a graph contains a closed loop.

For example:

TEXT
A
   / \
  B---C

The path:

TEXT
A → B → C → A

forms a cycle because:

  • It starts at A.
  • It visits other vertices.
  • It returns to A.
  • It does not repeat any intermediate vertex.

Types of Cycles

Undirected Graph Cycles

In an undirected graph, edges have no direction.

Example:

TEXT
A --- B
|     |
|     |
D --- C

A cycle exists:

TEXT
A → B → C → D → A

When detecting cycles in undirected graphs, a visited node alone is not enough. You must also track the parent node to avoid incorrectly identifying the edge you came from as a cycle.

Example:

TEXT
A --- B

When traversing from A to B, seeing A again from B is not a cycle. It is simply the same edge in the opposite direction.

Directed Graph Cycles

In a directed graph, edges have directions.

Example:

TEXT
A → B → C
↑       |
|_______|

The cycle is:

TEXT
A → B → C → A

Directed cycles are especially important in dependency problems. A cycle means there is no valid order to complete all tasks.

Detecting Cycles Using DFS

Depth-First Search (DFS) is commonly used to detect cycles.

For directed graphs, we track three states:

  • Unvisited: The node has not been explored.
  • Visiting: The node is currently in the DFS recursion stack.
  • Visited: The node and all its descendants have been fully explored.

If DFS reaches a node that is already in the visiting state, there is a cycle.

Example:

Python
def has_cycle(graph):
    state = {}


    def dfs(node):
        if state.get(node) == "visiting":
            return True


        if state.get(node) == "visited":
            return False


        state[node] = "visiting"


        for neighbor in graph[node]:
            if dfs(neighbor):
                return True


        state[node] = "visited"
        return False


    for node in graph:
        if dfs(node):
            return True


    return False

Example graph:

Python
graph = {
    "A": ["B"],
    "B": ["C"],
    "C": ["A"]
}

Traversal:

TEXT
A → B → C → A

Since A is encountered while it is still being explored, a cycle exists.

Cycle Detection in Undirected Graphs

For undirected graphs, DFS tracks the parent node:

Python
def has_cycle(graph):
    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


    return dfs(0, -1)

The neighbor != parent condition prevents the algorithm from treating the edge back to the previous node as a cycle.

Why Cycles Matter

Cycles are important because they can represent:

  • Circular dependencies.
  • Infinite loops.
  • Deadlocks.
  • Repeated routes.
  • Feedback relationships.

Examples:

  • A package manager cannot install packages if package A depends on B and B depends on A.
  • A task scheduler cannot determine an execution order if tasks depend on each other in a loop.
  • A web crawler must avoid revisiting pages indefinitely.

Real-world example

A software build system can be modeled as a directed graph:

  • Each file or package is a node.
  • A dependency is a directed edge.

Example:

TEXT
Application → Library A → Library B
                    ↑       |
                    |_______|

This contains a dependency cycle:

TEXT
Library A → Library B → Library A

A simple cycle check:

Python
dependencies = {
    "App": ["A"],
    "A": ["B"],
    "B": ["A"]
}


print(has_cycle(dependencies))

Output:

TEXT
True

A build tool would need to report this because there is no valid order in which the dependencies can be built.

Common mistakes

  • * Thinking a path and a cycle are the same thing.
  • * Forgetting that a cycle must return to its starting vertex.
  • * Detecting cycles in undirected graphs without tracking the parent node.
  • * Using the directed graph cycle detection method directly on undirected graphs.
  • * Assuming every graph with multiple paths contains a cycle.
  • * Forgetting that a self-loop (`A → A`) is a cycle.
  • * Ignoring disconnected components when checking whether an entire graph contains a cycle.

Follow-up questions

  • What is the difference between a path and a cycle in a graph?
  • How can you detect a cycle in an undirected graph using BFS?
  • Why do directed graphs use a recursion stack for cycle detection?
  • How are cycles related to topological sorting?
  • What is the time complexity of detecting a cycle using DFS?
  • Can a tree contain a cycle?

More Graph Theory interview questions

View all →