โปรแกรม Python ตรวจจับ Cycle ใน Directed Graph (กราฟมีทิศทาง)

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนด Directed Graph ให้ตรวจสอบว่ากราฟมี Cycle (วัฏจักร) หรือไม่ ผลลัพธ์ควรเป็น true หากกราฟมี Cycle อย่างน้อย 1 วัฏจักร มิฉะนั้นเป็น false

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# โมดูล collections
from collections import defaultdict

# คลาสสำหรับสร้างกราฟ
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):
        # ทำเครื่องหมายโหนดปัจจุบันว่า visited และเพิ่มเข้า recursion stack
        visited[v] = True
        recStack[v] = True
        # หากเพื่อนบ้านใดถูก visited และอยู่ใน recStack แสดงว่ากราฟเป็น cyclic
        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
        # นำโหนดออกหลังจบ recursion
        recStack[v] = False
        return False
    # คืนค่า True หากกราฟเป็น 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

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python เพื่อตรวจจับ Cycle ใน Directed Graph โดยใช้ DFS และ Recursion Stack