โปรแกรม 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 เพื่อตรวจจับวงจรในกราฟแบบกำหนดทิศทาง