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)