Detect Cycle in a Directed Graph/ Undirected Graph

Data Structures and Algorithms Note

Note: Depth First Traversal can be used to detect a cycle in a Graph

Detect Cycle in a Directed Graph

There are two situations the graph would be determined as having a cycle:

1. A back edge is from a node to itself (self-loop)
2. A node has an ancestor point to the node which is already been visited

In order to record which node has been visited and the visit process, we use two list visited and recstack. If the node’s linked vertices have not been visited, run check_cycle_util for linked vertices, otherwise, check that linked vertices is in the recstack or not, it means some node before the current node has already visited the linked vertices, and now we gonna visit it again, we could consider it as a cycle.

If there is no cycle found in check_cyckle_util, set recstack[v] back to False before ending the function. Or you could consider as when the v didn’t have a cycle, the recstack should be back to the previous status before continuing on the next call of check_cycle_util.

from collections import defaultdict
class Graph():
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices
    def add_edge(self, u, v):
        self.graph[u].append(v)
    def check_cycle_util(self, v, visited, recstack):
        visited[v] = True
        recstack[v] = True
        for linked_vertices in self.graph[v]:
          if not visited[linked_vertices]:
              if self.check_cycle_util(linked_vertices, visited, recstack):
                  return True
          elif recstack[linked_vertices]:
              return True
        
        recstack[v] = False
        return False

    def check_cycle(self):
        visited = [False] * (self.V)
        recstack = [False] * (self.V)
        for vertex in range(self.V):
            if not visited[vertex]:
                if self.check_cycle_util(vertex, visited, recstack):
                    return True
        return False

result

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(3, 0)
g.add_edge(3, 4)
g.add_edge(3, 3)
if g.check_cycle() == 1:
    print("Graph has a cycle")
else:
    print("Graph has no cycle")
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Graph has a cycle

another example

g = Graph(4)
g.add_edge(1, 0)
g.add_edge(2, 0)
g.add_edge(3, 1)
g.add_edge(3, 2)
if g.check_cycle() == 1:
    print("Graph has a cycle")
else:
    print("Graph has no cycle")
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Graph has no cycle

Detect Cycle in an Undirected Graph

The situation of detecting a cycle in an undirected graph is similar to directed graph, but for an undirected graph, we need one more condition: parent. If the adjacent node is not a parent and already visited then it is a cycle.

from collections import defaultdict
class Graph:
    def __init__(self,vertices):
        self.graph = defaultdict(list)
        self.V= vertices
        
    def add_edge(self,v,w):
        # Because the graph is undirected,
        # add two way for adjacent list
        # Add w to v_s list
        self.graph[v].append(w)
        # Add v to w_s list
        self.graph[w].append(v)
    def check_cycle_util(self, v, visited, parent):
        visited[v]= True
 
        for i in self.graph[v]:
            if  not visited[i]:
                if(self.check_cycle_util(i, visited, v)):
                    return True
            # If an adjacent vertex is visited
            # and not parent of current vertex,
            # then there is a cycle
            elif  parent != i:
                return True
        return False
          
    def check_cycle(self):
        visited =[False]*(self.V)
        for vertex in range(self.V):
            if not visited[vertex]:
                if self.check_cycle_util(vertex, visited,-1):
                    return True
        return False

result

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(3, 0)
g.add_edge(3, 4)
g.add_edge(3, 3)
if g.check_cycle() == 1:
    print("Graph has a cycle")
else:
    print("Graph has no cycle")
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Graph has a cycle

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