Chương trình Python phát hiện chu trình trong đồ thị có hướng

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho đồ thị có hướng, kiểm tra xem đồ thị có chứa chu trình (cycle) hay không. Trả về True nếu có ít nhất 1 chu trình, ngược lại False.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

from collections import defaultdict

# lớp đồ thị
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
        # nếu neighbor đã visited và trong recStack -> có chu trình
        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("Đồ thị có chu trình")
else:
    print("Đồ thị không có chu trình")

Kết quả

Đồ thị có chu trình

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python phát hiện chu trình trong đồ thị có hướng.