Câu hỏi:

26/06/2024 121

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.

Xem lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 12 KNTT Bài 15: Thực hành duyệt đồ thị theo chiều sâu có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

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.

Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

Trong lí thuyết đồ thị, chu trình được định nghĩa là một đường đi không tầm thường khép kín, tức là đường đi có số cạnh lớn hơn 1 và đỉnh xuất phát trùng với đỉnh kết thúc. Làm cách nào để kiểm tra một đồ thị cho trước có chu trình hay không?

Xem đáp án

Lời giải

Để kiểm tra xem một đồ thị có chu trình hay không, chúng ta có thể sử dụng thuật toán DFS (Duyệt Đầu Tiên) hoặc BFS (Duyệt Theo Chiều Rộng). Dưới đây là cách kiểm tra bằng DFS:

- Bắt đầu từ một đỉnh bất kỳ trong đồ thị.

- Thực hiện duyệt DFS từ đỉnh này.

- Trong quá trình duyệt, nếu đỉnh nào đã được thăm trước đó và không phải là đỉnh cha của đỉnh hiện tại (trong trường hợp của cây), tức là tìm thấy một chu trình.

- Nếu tất cả các đỉnh đều đã được duyệt và không tìm thấy chu trình, đồ thị không chứa chu trình.

Câu 2

Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu là vô hướng?

Xem đáp án

Lời giải

Để kiểm tra chu trình trong một đồ thị vô hướng, cách tiếp cận có thể khác so với đồ thị có hướng. Trong trường hợp đồ thị vô hướng, mỗi cạnh được coi là một liên kết giữa hai đỉnh, không có khái niệm đỉnh cha và đỉnh con.

Một cách để kiểm tra chu trình trong đồ thị vô hướng là sử dụng duyệt DFS nhưng cần phải theo dõi đỉnh trước đó mà không phải là đỉnh hiện tại (cha của đỉnh hiện tại) để tránh lặp lại qua cùng một cạnh. Nếu trong quá trình duyệt, gặp một đỉnh đã được thăm trước đó và không phải là đỉnh cha của đỉnh hiện tại, thì có thể kết luận rằng đồ thị chứa chu trình.

Câu 3