Câu hỏi:
26/06/2024 71Viế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.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lờ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.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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 hoặc danh sách kề Adj. Viết hàm kiểm tra xem đồ thị G có chu trình hay không, nếu có thì hiển thị trên màn hình chu trình đó, bao gồm dãy các đỉnh tham gia vào 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?
Câu 3:
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?
Câu 4:
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í thì thông báo dãy các chuyên đề có mâu thuẫn về kiến thức.
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 1
về câu hỏi!