Câu hỏi:
13/07/2024 44Với các thông tin về tuyến xe buýt giữa các địa điểm được biểu diễn bằng ma trận kể như Hình 13. Em áp dụng thuật toán duyệt theo chiều rộng hoặc theo chiều sâu để chỉ ra các địa điểm có thế đến được nếu xuất phát địa điểm 0 và chỉ sử dụng các tuyến xe buýt này.
Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 160k).
Quảng cáo
Trả lời:
Với các thông tin về tuyến xe buýt giữa các địa điểm được biểu diễn bằng ma trận kể như Hình 13. Em áp dụng thuật toán duyệt theo chiều rộng hoặc theo chiều sâu để chỉ ra các địa điểm có thế đến được nếu xuất phát địa điểm 0 và chỉ sử dụng các tuyến xe buýt này như sau:
* Duyệt theo chiều rộng (BFS) như sau:
Chúng ta sẽ sử dụng BFS để tìm các địa điểm có thể đến được từ địa điểm 0.
- Khởi tạo: Đặt một hàng đợi để lưu trữ các địa điểm cần khám phá. Bắt đầu với địa điểm 0. Đánh dấu địa điểm 0 là đã được thăm. Tạo một danh sách để lưu trữ các địa điểm đã đến được.
- Thuật toán: Lặp lại cho đến khi hàng đợi rỗng:
+ Lấy địa điểm đầu tiên ra khỏi hàng đợi.
+ Khám phá tất cả các địa điểm kết nối trực tiếp với địa điểm hiện tại (theo ma trận kề).
+ Nếu địa điểm chưa được thăm, thêm nó vào hàng đợi và đánh dấu là đã thăm.
* Mã giả cho BFS
def bfs(graph, start):
visited = [False] * len(graph)
queue = []
reachable = []
queue.append(start)
visited[start] = True
while queue:
node = queue.pop(0)
reachable.append(node)
for i in range(len(graph[node])):
if graph[node][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
return reachable
# Ma trận kề
graph = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 1, 1, 0]
]
# Xuất phát từ địa điểm 0
start = 0
reachable_locations = bfs(graph, start)
print("Các địa điểm có thể đến được từ địa điểm 0:", reachable_locations)
Kết quả như sau: Các địa điểm có thể đến được từ địa điểm 0 là: [0, 1, 3, 2]
Đã bán 152
Đã bán 114
Đã bán 132
Đã bán 47
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Trong các câu sau đây, những câu nào đúng khi nói về duyệt đồ thị?
a) Duyệt đồ thị theo chiều sâu giúp ta xác định các đỉnh có thể tới được từ một đinh bất kì.
b) Duyệt đồ thị theo chiều rộng không thể giúp ta xác định các đỉnh có thể tới được từ một đỉnh bất kì.
c) Thứ tự thăm các đỉnh khi thực hiện cách duyệt đồ thị theo chiều rộng và theo chiều sâu sẽ giống hệt nhau.
d) Để duyệt đồ thị theo chiều rộng chúng ta sử dụng hàng đợi, thăm các đỉnh theo nguyên tắc vào trước ra trước.
c) Để duyệt đồ thị theo chiều sâu chúng ta sử dụng ngăn xếp, thăm các đinh theo nguyên tắc vào sau ra trước.
Câu 2:
Có 5 bạn A, B, C, D và E, biết rằng A có số điện thoại của C và D, do đó A có thể liên lạc với C, D; tương tự B có số điện thoại của A; C có số điện thoại của B; D có số điện thoại của C; E có số điện thoại của D. Nếu biểu diễn A, B, C, D, E là các đỉnh của đồ thị và xét mối quan hệ có số điện thoại (có thể liên lạc), ta có đồ thị như Hình 1. Em hãy cho biết nếu A cần thông báo một thông tin thì những ai có thể nhận được thông tin đó. Câu hỏi tương tự nếu người cần thông báo thông tin là E.
về câu hỏi!