방향 그래프에서 주기 감지를 위한 Python 프로그램

이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.

문제 설명 − 방향 그래프가 주어졌을 때 그래프에 주기가 포함되어 있는지 확인해야 합니다. 주어진 그래프에 하나 이상의 주기가 포함되어 있으면 출력이 true여야 하고, 그렇지 않으면 false입니다.

이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -

예시

# collections module
from collections import defaultdict
# class for creation of graphs
class Graph():
   # constructor
   def __init__(self, vertices):
      self.graph = defaultdict(list)
      self.V = vertices
   def addEdge(self, u, v):
      self.graph[u].append(v)
   def isCyclicUtil(self, v, visited, recStack):
      # Marking current node visited and addition to recursion stack
      visited[v] = True
      recStack[v] = True
      # if any neighbour is visited and in recStack then graph is cyclic in nature
      for neighbour in self.graph[v]:
         if visited[neighbour] == False:
            if self.isCyclicUtil(neighbour, visited, recStack) == True:
               return True
         elif recStack[neighbour] == True:
            return True
      # pop the node after the end of recursion
      recStack[v] = False
      return False
   # Returns true if graph is cyclic
   def isCyclic(self):
      visited = [False] * self.V
      recStack = [False] * self.V
      for node in range(self.V):
         if visited[node] == False:
            if self.isCyclicUtil(node, visited, recStack) == True:
               return True
      return False
g = Graph(4)
g.addEdge(0, 3)
g.addEdge(0, 2)
g.addEdge(3, 2)
g.addEdge(2, 0)
g.addEdge(1, 3)
g.addEdge(2, 1)
if g.isCyclic() == 1:
   print ("Graph is cyclic in nature")
else:
   print ("Graph is non-cyclic in nature")

출력

Graph is cyclic in nature

모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.

결론

이 기사에서는 방향 그래프에서 주기를 감지하는 Python 프로그램을 만드는 방법에 대해 배웠습니다.