Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A
Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A thay thế cho danh sách kề Adj.
Giải Chuyên đề Tin 12 Bài 17: Thực hành duyệt đồ thị tổng hợp - Kết nối tri thức
Luyện tập 2 trang 82 Chuyên đề Tin học 12: Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A thay thế cho danh sách kề Adj.
Lời giải:
Viết lại hàm BFS sử dụng ma trận kề A thay vì danh sách kề Adj. Dưới đây là cách triển khai:
from collections import deque
def BFS(graph, start):
n = len(graph)
visited = [False] * n
visited[start] = True
queue = deque([start])
while queue:
vertex = queue.popleft()
print("Visit:", vertex)
for neighbor in range(n):
if graph[vertex][neighbor] == 1 and not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
# Ma trận kề mẫu
graph_matrix = [
[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0]
]
# Thực hiện BFS từ đỉnh 0
BFS(graph_matrix, 0)
- Trong hàm BFS này, chúng ta duyệt qua các hàng của ma trận kề để xác định các đỉnh kề của mỗi đỉnh. Nếu có một đỉnh kề chưa được duyệt, chúng ta đánh dấu đỉnh đó đã được thăm và thêm nó vào hàng đợi để duyệt tiếp.
Lời giải bài tập Chuyên đề Tin 12 Bài 17: Thực hành duyệt đồ thị tổng hợp hay, ngắn gọn khác: