Câu hỏi:
26/06/2024 22Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lờ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.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Thiết lập hàm printpath(s,t) không đệ quy có tính năng tương tự hàm cùng tên trong chương trình trên.
Câu 2:
Sửa lại phần nhập dữ liệu hai học sinh: sẽ nhập trực tiếp tên hai học sinh, kiểm tra các tên này có nhập đúng không và thực hiện yêu cầu như trong chương trình trên.
Câu 3:
Câu 4:
Trong bài thực hành trước chúng ta đã được ôn tập và giải một số bài toán có áp dụng thuật toán duyệt đồ thị theo chiều sâu. Còn về thuật toán duyệt theo chiều rộng em có biết gì về các ứng dụng thực tế của bài toán này không?
về câu hỏi!