Detect Cycle in a Graph

6 min readOct 6, 2022

Perform Depth First Search(DFS) traversal on a graph to detect cycle. In a directed graph, apply white-grey-black cycle detection to determine whether if a cycle is present or not. While in an undirected graph, keep track of visited nodes and the parent of each node to prevent backtracking to them. If a visited node (exclude the parent node) is found, the graph is cyclic.

Table of Contents· Cycle in a Graph
· Detect Cycle using DFS
  ∘ Types of Edges in DFS
  ∘ Back Edges → Cycle
· Detect Cycle in a Directed Graph
  ∘ White-Grey-Black Cycle Detection
  ∘ Approach: DFS + White-Grey-Black Cycle Detection
  ∘ Graphical Explanation
  ∘ Code Implementation
· Detect Cycle in an Undirected Graph
  ∘ White-Grey-Black Cycle Detection Does Not Work in an Undirected Graph
  ∘ Approach: DFS + Visited Nodes + Parent Node
  ∘ Graphical Explanation
  ∘ Code Implementation

Cycle in a Graph

A cycle is a path that starts and ends at the same node in a graph.

Detect Cycle using DFS

Depth First Search(DFS) is a graph traversal algorithm that start at a given node and explore each branch as deep as possible before backtracking. That is, it goes deep before it goes wide.

Types of Edges in DFS

After a DFS traversal of a graph, only some edges were traversed. These edges constructed a tree, called the DFS tree. There are different edges types in a graph.

Tree edge: an edge is present in the DFS tree
Back edge: an edge from a vertex to a previously visited vertex that is an ancestor
Forward edge: an edge from a vertex to a previously visited vertex that is a descendant
Cross edge: an edge from a vertex to a previously visited vertex that is neither an ancestor or a descendant.

Forward edges and cross edges are only occurred in directed graphs.

Back Edges → Cycle

The presence of back edges in a graph implies a cycle is existed. Therefore, the purpose of cycle detection is to find whether a back edge is existed in the graph or not.

Detect Cycle in a Directed Graph

LeetCode 207: Course Schedule

Perform a DFS on a directed graph, the graph can contain four types of edges, tree, back, cross and forward edges. If we only keep track of the nodes we have been visited, we will have limited information to identify a back edge in the graph. A back edge is an edge from a node to a visited node that is one of its ancestors. That’s why white-grey-black cycle detection comes in handy. Aside from a visited state, it introduces an extra state, visiting, to track ancestors.

White-Grey-Black Cycle Detection

Use three colors to label the state of nodes as we traverse through them. White color of a node is unexplored, grey color is for a node which is during recursively exploring its descendants/neighbors and black color of a node is a visited node which all its descendants have been completely visited.

white: unexplored
grey: visiting(during recursively visiting its descendants)
black: visited(all of its descendants have been visited)

Basically, a white node turns grey once we visit it but haven’t travel through all its descendants. A grey node becomes black until all its descendant are being visited.

If a node is seen again before all its descendants have been discovered, there is a back edge. That is, if a grey node has a descendant which is grey, it is a cyclic graph.

Approach: DFS + White-Grey-Black Cycle Detection

If the given graph is a disconnected graph, iterate through each node and DFS at the unvisited node.

DFS traversal at the start node. If the node is unexplored, we begin visiting it and apply white-gray-back cycle detection to determine whether a cycle is present or not.

Graphical Explanation

step1: convert edges to an adjacency list for easier to traverse later

step2: DFS traversal at the start node

Code Implementation

Complexity
Time: O(v+e)
Space: O(v)
v: the total number of vertices in the graph
e: the total number of edges in the graph
Golang

Python

Detect Cycle in an Undirected Graph

White-Grey-Black Cycle Detection Does Not Work in an Undirected Graph

In an undirected graph the edges are bidirectional. An undirected edge {u, v} can be defined as two directed edges, (u, v) and (v, u), which would be consider as a cycle by white-grey-black cycle detection. That’s why white-grey-black cycle detection doesn’t work in an undirected graph.

To avoid finding a cycle between two nodes connected by an edge, we need to remember a node’s parent to prevent going back to the parent.

Approach: DFS + Visited Nodes + Parent Node

If the given graph is a disconnected connected graph, iterate through each node and DFS at the unvisited node.

DFS traversal at the start node. Keep track of visited nodes and the parent node of each node to avoid backtracking to them. If a visited node that is not a parent node is encountered, a cycle is detected.