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
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.
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: