Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A
Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A của đồ thị.
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
Luyện tập 2 trang 79 Chuyên đề Tin học 12: Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A của đồ thị.
Lời giải:
Gợi ý viết tổng quát của hàm BFS sử dụng ma trận kề của đồ thị:
from collections import deque
def BFS(matrix, start):
n = len(matrix) # Số lượng đỉnh trong đồ thị
visited = set() # Sử dụng một set để lưu trữ các đỉnh đã được duyệt
queue = deque([start]) # Khởi tạo hàng đợi và thêm đỉnh bắt đầu vào đó
while queue:
vertex = queue.popleft() # Lấy đỉnh ở đầu hàng đợi ra
if vertex not in visited:
print("Visit:", vertex) # In ra đỉnh đã duyệt
visited.add(vertex) # Đánh dấu đỉnh đã duyệt
for neighbor in range(n): # Duyệt qua tất cả các đỉnh
if matrix[vertex][neighbor] == 1 and neighbor not in visited:
queue.append(neighbor) # Thêm các đỉnh kề chưa được duyệt vào hàng đợi
# Đồ thị mẫu dưới dạng ma trận kề
graph_matrix = [
[0, 1, 1, 0, 0, 0], # A
[1, 0, 0, 1, 1, 0], # B
[1, 0, 0, 0, 0, 1], # C
[0, 1, 0, 0, 0, 0], # D
[0, 1, 0, 0, 0, 1], # E
[0, 0, 1, 0, 1, 0] # F
]
# Thực hiện BFS từ đỉnh 0 (tương ứng với đỉnh 'A')
BFS(graph_matrix, 0)
- Chú ý: Trong hàm BFS này, ta sử dụng ma trận kề matrix để xác định các đỉnh kề của mỗi đỉnh. Nếu một đỉnh kề chưa được duyệt, ta thêm nó vào hàng đợi để duyệt tiếp. Quá trình này được lặp lại cho tất cả các đỉnh kề của mỗi đỉnh được duyệt.
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: