In this article, you will learn to use Depth-First Search algorithms to detect a cycle in a directed graph

Unlike in an undirected graph, to detect a cycle in a directed graph you should consider the direction of the edges

Learn about the type of graphs

Let's get started

Problem

  • Given a directed graph G = (V, E)

  • Write an algorithm to detect a cycle in that graph

Example 1

  • Input: Given a directed graph G = (V, E) with V = 5 and E = [[0, 1], [1, 2], [2, 0], [1, 3], [2, 4]]

  • Output: true

Example 2

  • Input: Given a directed graph G = (V, E) with V = 4 and E = [[0, 1], [2, 0], [2, 1], [3, 2]]

  • Output: false

Approach 1: DFS Iterative

  • Use a stack to track the traversal path

  • Keeping track of the visited and on-stack state of each vertex

    While visiting a vertex and its adjacencies, if we ever encounter an on-stack vertex then the graph has a cycle


GraphDirectedByAdjacencyList is defined in Graph Data Structure Tutorial

  • Output
true  
false  
  • Time complexity: O(V+E)

  • Space complexity: O(V)

Approach 2: DFS Recursive

  • Instead of using a stack, the algorithm calls to itself to explore unvisited vertices

  • Keeping track of the visited and on-stack state of each vertex

    While visiting a vertex and its adjacencies, if we ever encounter an on-stack vertex then the graph has a cycle


GraphDirectedByAdjacencyList is defined in Graph Data Structure Tutorial

  • Output
true  
false  
  • Time complexity: O(V+E)

  • Space complexity: O(V)

Approach 3: DFS Iterative with Color

  • Use a stack to track the traversal path

  • Keeping track of the unvisited (White color), visit in progress (Gray color, the vertex is on the stack) and visited state (Black color) of each vertex.

    While visiting a vertex and its adjacencies, if we ever encounter a gray vertex then the graph has a cycle


GraphDirectedByAdjacencyList is defined in Graph Data Structure Tutorial

  • Output
true  
false  
  • Time complexity: O(V+E)

  • Space complexity: O(V)

Approach 4: DFS Recursive with Color

  • Instead of using a stack, the algorithm calls to itself to explore unvisited vertices

  • Keeping track of the unvisited (White color), visit in progress (Gray color, the vertex is on the stack) and visited state (Black color) of each vertex

    While visiting a vertex and its adjacencies, if we ever encounter a gray vertex then the graph has a cycle


GraphDirectedByAdjacencyList is defined in Graph Data Structure Tutorial

  • Output
true  
false  
  • Time complexity: O(V+E)

  • Space complexity: O(V)