資料結構
網路
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 次瀏覽
廣告