Viết lại hàm kiểm tra chu trình DFS_acyclic(Adj,s) trong chương trình trên nhưng sử dụng phương án không đệ quy của thuật toán DFS.

Phiên bản mẫu của hàm DFS_acyclic sử dụng phương pháp không đệ quy của thuật toán DFS để kiểm tra xem một đồ thị có chứa chu trình hay không:

def DFS_acyclic(Adj, s):

    stack = [(s, None)]  # Dùng stack để thực hiện DFS, cặp (đỉnh, đỉnh cha)

    visited = set()  # Dùng set để theo dõi các đỉnh đã thăm

    while stack:

        node, parent = stack.pop()  # Lấy đỉnh ra khỏi stack

        if node in visited:  # Nếu đỉnh đã được thăm trước đó

            return True  # Tìm thấy chu trình

        visited.add(node)  # Đánh dấu đỉnh đã thăm

        for neighbor in Adj[node]:  # Duyệt các đỉnh kề của đỉnh hiện tại

            if neighbor != parent:  # Tránh quay lại đỉnh cha

                stack.append((neighbor, node))  # Thêm đỉnh kề vào stack

    return False  # Không tìm thấy chu trình

# Sử dụng hàm kiểm tra chu trình không đệ quy

graph_undirected = {

    0: [1, 2],

    1: [0, 3],

    2: [0, 3],

    3: [1, 2]

}

if DFS_acyclic(graph_undirected, 0):

    print("Đồ thị vô hướng có chu trình")

else:

    print("Đồ thị vô hướng không có chu trình")

Trong hàm này:

• Chúng ta sử dụng một stack để thực hiện duyệt DFS thay vì đệ quy.
• Mỗi lần duyệt, chúng ta kiểm tra xem đỉnh hiện tại đã được thăm trước đó chưa. Nếu có, chúng ta tìm thấy chu trình.
• Nếu không, chúng ta đánh dấu đỉnh đó đã được thăm và duyệt qua tất cả các đỉnh kề của nó, tránh quay lại đỉnh.