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

Giải Chuyên đề Tin 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu - Kết nối tri thức

Luyện tập 2 trang 74 Chuyên đề Tin học 12: 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.

Lời giải:

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.

Lời giải bài tập Chuyên đề Tin 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu hay, ngắn gọn khác:

• Khởi động trang 72 Chuyên đề Tin học 12: Trong lí thuyết đồ thị, chu trình được định nghĩa là một đường đi không tầm thường ....

• Luyện tập 2 trang 74 Chuyên đề Tin học 12: Viết lại hàm kiểm tra chu trình DFS_acyclic(Adj,s) trong chương trình ....

• Vận dụng 1 trang 74 Chuyên đề Tin học 12: Sửa lại chương trình bổ sung thông báo nếu hệ thống chuyên đề không hợp lí ....

• Vận dụng 2 trang 74 Chuyên đề Tin học 12: Mở rộng bài tập trên cho đồ thị có hướng bất kì G = (V, E), được biểu diễn bởi ma trận kề A ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

• Chuyên đề Tin học 12 Bài 17: Thực hành duyệt đồ thị tổng hợp

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---