Detecting Cycle in a Graph using DFS Algorithm in Python

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())

Github: AR-Shahin