Quảng cáo
1 câu trả lời 120
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.
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
149615 -
Đã trả lời bởi chuyên gia
99992 -
Đã trả lời bởi chuyên gia
97600 -
Đã trả lời bởi chuyên gia
80297 -
Đã trả lời bởi chuyên gia
73088 -
Đã trả lời bởi chuyên gia
56178 -
Đã trả lời bởi chuyên gia
55554
