数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装学
法学Python 程序用于检测有向图中的环
在本文中，我们将学习如何解决下面给出的问题陈述。
问题陈述 －给定一个有向图，我们需要检查图形中是否包含循环。如果给定的图至少包含一个循环，则输出为真，否则为假。
下面让我们观察实现中给出的解决方案 －
示例
# 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 程序来检测有向图中的循环。
更新时间： 2019-12-20
906 次浏览
广告