有向グラフでサイクルを検出するためのPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 −有向グラフが与えられたので、グラフにサイクルが含まれているかどうかを確認する必要があります。指定されたグラフに少なくとも1つのサイクルが含まれている場合、出力は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プログラムを作成する方法について学びました