ডায়রেক্টেড গ্রাফে সাইকেল ডিটেক্ট করার পাইথন প্রোগ্রাম

এই আর্টিকেলে আমরা নিচের সমস্যা সমাধানের কথা শিখব।

সমস্যা: একটি ডায়রেক্টেড গ্রাফ দেওয়া আছে, আমাদের চেক করতে হবে যে গ্রাফে সাইকেল আছে কিনা। আউটপুট true হবে যদি গ্রাফে কমপক্ষে একটি সাইকেল থাকে, অন্যথায় false।

চলুন নিচের ইমপ্লিমেন্টেশনে সমাধানটি পর্যবেক্ষণ করি।

উদাহরণ

# 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")

আউটপুট

Graph is cyclic in nature

সभी ভেরিয়েবল লোকাল স্কোপে ঘোষণা করা হয়েছে এবং তাদের রেফারেন্স উপরের চিত্রে দেখা যাচ্ছে।

উপসংহার

এই আর্টিকেলে আমরা শিখেছি কিভাবে ডায়রেক্টেড গ্রাফে সাইকেল ডিটেক্ট করার পাইথন প্রোগ্রাম লিখতে হয়।