5. Detect cycle in directed graph using dfs

Detect Cycle in an undirected graph¶

References¶

1. https://www.geeksforgeeks.org/detect-cycle-in-a-graph/

In [1]:

from utils.graph import GraphAdjList as Graph
from utils.graph_properties import GraphPropertiesAdjList as gp

from utils.graph import GraphAdjList as Graph from utils.graph_properties import GraphPropertiesAdjList as gp

In [2]:

g = Graph()
g.insert_node(0, 1)
g.insert_node(0, 2)
g.insert_node(1, 2)
g.insert_node(2, 0)
g.insert_node(2, 3)
g.insert_node(3, 3)

g = Graph() g.insert_node(0, 1) g.insert_node(0, 2) g.insert_node(1, 2) g.insert_node(2, 0) g.insert_node(2, 3) g.insert_node(3, 3)

In [3]:

class checkCycle:
    def __init__(self, graph):
        self.graph = graph
        self.num_vertices = gp.num_vertices(self.graph)
        self.visited = [False] * self.num_vertices
        self.dfs_stack = [False] * self.num_vertices

    def has_cycle(self, node):

        self.visited[node] = True
        self.dfs_stack[node] = True

        for neighbour in self.graph[node]:
            if self.visited[neighbour] == False:
                if self.has_cycle(neighbour):
                    return True
            elif self.dfs_stack[neighbour]:
                return True

        self.dfs_stack[node] = False
        return False

    def is_cyclic_util(self):

        for vertex in range(self.num_vertices):
            if self.visited[vertex] == False:
                if self.has_cycle(vertex):
                    return True

        return False

class checkCycle: def __init__(self, graph): self.graph = graph self.num_vertices = gp.num_vertices(self.graph) self.visited = [False] * self.num_vertices self.dfs_stack = [False] * self.num_vertices def has_cycle(self, node): self.visited[node] = True self.dfs_stack[node] = True for neighbour in self.graph[node]: if self.visited[neighbour] == False: if self.has_cycle(neighbour): return True elif self.dfs_stack[neighbour]: return True self.dfs_stack[node] = False return False def is_cyclic_util(self): for vertex in range(self.num_vertices): if self.visited[vertex] == False: if self.has_cycle(vertex): return True return False

In [4]:

obj = checkCycle(g.graph)

obj = checkCycle(g.graph)

In [5]:

obj.is_cyclic_util()

obj.is_cyclic_util()

Out[5]:

True

In [ ]: