Cho đơn đồ thị vô hướng G = V, E. Sử dụng thuật toán duyệt theo chiều rộng BFS
Cho đơn đồ thị vô hướng G = (V, E). Sử dụng thuật toán duyệt theo chiều rộng BFS, viết chương trình kiểm tra xem G có chu trình hay không. Chu trình (cycle) ở đây được hiểu là một đường đi khép kín, đỉnh xuất phát trùng với đỉnh kết thúc. Cần thiết lập hàm dạng Acycle(G), hàm trả lại True nếu G không có chu trình, ngược lại hàm trả lại False.
Giải Chuyên đề Tin 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng - Kết nối tri thức
Vận dụng 1 trang 79 Chuyên đề Tin học 12: Cho đơn đồ thị vô hướng G = (V, E). Sử dụng thuật toán duyệt theo chiều rộng BFS, viết chương trình kiểm tra xem G có chu trình hay không. Chu trình (cycle) ở đây được hiểu là một đường đi khép kín, đỉnh xuất phát trùng với đỉnh kết thúc. Cần thiết lập hàm dạng Acycle(G), hàm trả lại True nếu G không có chu trình, ngược lại hàm trả lại False.
Lời giải:
Để kiểm tra xem đồ thị có chu trình hay không, ta có thể sử dụng thuật toán BFS để duyệt đồ thị và kiểm tra xem có đỉnh nào được duyệt lại không. Nếu có đỉnh nào đã được duyệt và nó là đỉnh kề của đỉnh hiện tại, thì đồ thị chứa chu trình.
Dưới đây là một cài đặt Python cho hàm Acycle(G):
from collections import deque
def Acycle(G):
# Hàm kiểm tra có chu trình hay không
def has_cycle(graph, start):
visited = set()
queue = deque([(start, None)]) # Lưu trữ cả cạnh đến đỉnh đang duyệt
while queue:
vertex, parent = queue.popleft()
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor != parent: # Loại bỏ trường hợp quay lại đỉnh cha
if neighbor in visited:
return True # Đồ thị có chu trình
else:
queue.append((neighbor, vertex)) # Thêm đỉnh kề vào hàng đợi
return False # Đồ thị không có chu trình
# Duyệt qua tất cả các đỉnh của đồ thị
for vertex in G:
if has_cycle(G, vertex):
return False # Nếu có chu trình, trả về False
return True # Nếu không có chu trình, trả về True
# Ví dụ về đồ thị được biểu diễn bằng danh sách kề
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Kiểm tra đồ thị có chu trình hay không
print(Acycle(graph)) # False
- Chú ý: Trong hàm Acycle(G), ta duyệt qua tất cả các đỉnh của đồ thị và sử dụng hàm has_cycle(graph, start) để kiểm tra xem có chu trình bắt đầu từ đỉnh đó hay không. Nếu ta tìm thấy bất kỳ chu trình nào, ta trả về False. Nếu không có chu trình nào được tìm thấy, ta trả về True.
Lời giải bài tập Chuyên đề Tin 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng hay, ngắn gọn khác: