Detecting cycle in graph in a graph we can use the DFS Algorithm. Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is joining a node to itself (self-loop) or one of its ancestors in the tree produced by DFS.

### Learn Laravel

In this tutorial, We are going to see how to detect cycles in a graph using DFS. Well, before jumping this tutorial, you have to know how to implement **DFS** (Depth First Traversal ) algorithm. Because we will modify the DFS algorithm a bit to find the cycle.

##### Prerequisite : Implement DFS traversal algorithm using python

Well, I assume that you are familiar with the **DFS** algorithm. In this tutorial, we will use this graph to detect the cycle or not which is a directed graph. Also, we will check our algorithm using an undirected graph.

Well, in this graph, there are five nodes and five edges that are directed. Let’s see the adjacency list of this graph.

```
nodes = ["A", "B", "C", "D", "E"]
edges = [
("A", "C"),
("A", "B"),
("B", "D"),
("D", "A"),
("D", "E"),
]
```

Well, now see the algorithm of detecting the cycle. Let’s see the code, I will explain you later.

```
class DetectCycle(Graph):
def __init__(self, nodes, edges, is_directed=False):
super().__init__(nodes, is_directed)
self.add_multiple_edges(edges)
self.color = {}
self.parent = {}
self.output = []
self.is_cycle = False
for node in self.adj_list.keys():
self.color[node] = "W"
self.parent[node] = None
```

I assume you are familiar with this code because I have explained it a couple of times. If you want an explanation of this code you may read this blog. I just add a new variable that is the **is_cycle**. Initially, this value is equal to **False**.

### Cycle detect in a Graph

```
def detect_cycle(self, source):
self.color[source] = "G"
self.output.append(source)
for v in self.adj_list[source]:
if self.color[v] == "W":
self.parent[v] = source
cycle = self.detect_cycle(v)
if cycle:
self.is_cycle = True
return True
elif self.color[v] == "G" and self.parent[source] != v:
self.is_cycle = True
return True
self.color[source] = "B"
return False
```

Well, now I am going to explain these pieces of code. As it is like **DFS**, we send a parameter in this function, and initially, assign the source node’s color is from **white** to **Gray**. Well, then push this source in the output list.

Well, after then traverse all unvisited neighbors of the source node. Then push parent of neighbor is the source. After then call again the function parameter with an unvisited neighbor and store it in a variable. Then check a condition, if the conditions are fulfilled then change is_cycle value **False** to **True** and return **True** from this function.

After then checking another condition, if the color of a neighbor is Gray and the parent of the source is not equal to the neighbor then return True as well change **is_cycle** value. After the loop, change the color of the source node is **Black** and return **False**.

### Print cyclic Path

If you want to print the cyclic path of the graph you can use this code.

```
def print_cycle_path(self):
if self.is_cycle:
return self.output[:-1]
```

Now time to check our code by a directed graph.

```
nodes = ["A", "B", "C", "D", "E"]
edges = [
("A", "C"),
("A", "B"),
("B", "D"),
("D", "A"),
("D", "E"),
]
dc = DetectCycle(nodes, edges, True)
print(dc.detect_cycle("A"))
print(dc.print_cycle_path())
// Output
True
['A', 'C', 'B']
```

Now check using an undirected graph.

```
nodes = ["A", "B", "C", "D", "E"]
undirected = [
("A", "B"),
("A", "D"),
("B", "C"),
("C", "D"),
("D", "E")
]
dc = DetectCycle(nodes, edges, False)
print(dc.detect_cycle("A"))
print(dc.print_cycle_path())
// Output
True
```

#### Full code

```
from graph import Graph
class DetectCycle(Graph):
def __init__(self, nodes, edges, is_directed=False):
super().__init__(nodes, is_directed)
self.add_multiple_edges(edges)
self.color = {}
self.parent = {}
self.output = []
self.is_cycle = False
for node in self.adj_list.keys():
self.color[node] = "W"
self.parent[node] = None
def detect_cycle(self, source):
self.color[source] = "G"
self.output.append(source)
for v in self.adj_list[source]:
if self.color[v] == "W":
self.parent[v] = source
cycle = self.detect_cycle(v)
if cycle:
self.is_cycle = True
return True
elif self.color[v] == "G" and self.parent[source] != v:
self.is_cycle = True
return True
self.color[source] = "B"
return False
def print_cycle_path(self):
if self.is_cycle:
return self.output
# edges = [
# ("A", "B"),
# ("C", "B"),
# ("C", "D"),
# ("D", "E"),
# ]
undirected = [
("A", "B"),
("A", "D"),
("B", "C"),
("C", "D"),
("D", "E")
]
edges = [
("A", "C"),
("A", "B"),
("B", "D"),
("D", "A"),
("D", "E"),
]
nodes = ["A", "B", "C", "D", "E"]
undirected = [
("A", "B"),
("A", "D"),
("B", "C"),
("C", "D"),
("D", "E")
]
dc = DetectCycle(nodes, edges, False)
print(dc.detect_cycle("A"))
print(dc.print_cycle_path())
```