用于检测有向图中的循环的 Python 程序

pythonserver side programmingprogramming

在本文中，我们将了解下面给出的问题陈述的解决方案。

问题陈述 − 给定一个有向图，我们需要检查该图是否包含循环。如果给定的图至少包含一个循环，则输出应为真，否则为假。

现在让我们观察下面实现中的解决方案 −

示例

# collections 模块
from collections import defaultdict
# 用于创建图的类
class Graph():
   # 构造函数
   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):
      # 标记当前节点已访问并添加到递归堆栈
      visited[v] = True
      recStack[v] = True
      # 如果任何邻居被访问且在 recStack 中，则图本质上是循环的
      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
        # 递归结束后弹出节点
      recStack[v] = False
      return False
   # 如果图是循环的，则返回 true
   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")