पायथन प्रोग्राम: निर्देशित ग्राफ में चक्र का पता लगाएं

इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे।

समस्या कथन

हमें एक निर्देशित ग्राफ दिया गया है, हमें जांचना है कि ग्राफ में चक्र है या नहीं। आउटपुट सच होना चाहिए यदि दिया गया ग्राफ कम से कम एक चक्र रखता है, अन्यथा गलत।

उदाहरण

# 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
    # सच लौटाता है यदि ग्राफ चक्रीय है
    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

निष्कर्ष

इस लेख में हमने निर्देशित ग्राफ में चक्र का पता लगाने के पायथन प्रोग्राम के बारे में सीखा।