Câu hỏi:
04/10/2024 25Viết chương trình đếm số nước liên minh với nước đã cho
Yêu cầu: Có N nước, các nước được chia thành các liên minh. Quan hệ liên minh như sau:
nếu nước A liên minh với nước B, nước B liên minh với nước C thì nước A liên minh với nước C. Cho biết nước X, sử dụng thuật toán duyệt đồ thị theo chiều rộng, hãy cho biết có bao nhiêu nước liên minh với nước X.
Dữ liệu vào: Tệp lienminh.txt chứa dữ liệu của các nước. Hàng đầu tiên là danh sách các nước. Các hàng kế tiếp: mỗi hàng chứa một cạnh gồm hai nước liên minh. Hàng cuối cùng là nước X.
Dữ liệu ra: Số nước liên minh với nước X.
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:
Để giải quyết bài toán này, chúng ta sẽ sử dụng thuật toán duyệt đồ thị theo chiều rộng (BFS - Breadth-First Search). Thuật toán này sẽ giúp chúng ta xác định số lượng nước liên minh với nước X từ dữ liệu đã cho.
Các bước giải quyết bài toán:
Đọc dữ liệu từ file: Đọc danh sách các nước và các liên minh từ tệp lienminh.txt. Hàng đầu tiên là danh sách các nước, các hàng tiếp theo là các cặp nước liên minh, và hàng cuối cùng là nước X cần xác định số nước liên minh.
Biểu diễn đồ thị: Sử dụng một danh sách kề để lưu trữ các nước liên minh với nhau.
Duyệt đồ thị bằng BFS: Bắt đầu từ nước X, sử dụng BFS để duyệt qua tất cả các nước liên minh và đếm số lượng nước liên minh này.
Xuất kết quả: In ra số lượng nước liên minh với nước X.
Dưới đây là mã Python để giải quyết bài toán:
from collections import defaultdict, deque
def read_graph_data(filename):
adjacency_list = defaultdict(list)
start_node = None
with open(filename, 'r') as f:
lines = f.readlines()
countries = lines[0].strip().split()
for line in lines[1:]:
if line.strip() == '':
continue
node1, node2 = line.strip().split()
if start_node is None:
start_node = node1
adjacency_list[node1].append(node2)
adjacency_list[node2].append(node1)
x_country = lines[-1].strip()
return countries, adjacency_list, x_country
def bfs_count_connected(adjacency_list, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in adjacency_list[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return count
def main():
filename = 'lienminh.txt'
countries, adjacency_list, x_country = read_graph_data(filename)
if x_country not in adjacency_list:
print(f"Nước {x_country} không có trong danh sách các nước liên minh.")
return
num_connected_countries = bfs_count_connected(adjacency_list, x_country)
print(f"Số nước liên minh với nước {x_country} là: {num_connected_countries}")
if __name__ == "__main__":
main()
Đã bán 152
Đã bán 114
Đã bán 132
Đã bán 47
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Chương trình dưới đây duyệt đồ thị G3 (Hình 3) bắt đầu từ đỉnh B và đỉnh F. Em có nhận xét gì về thứ tự duyệt bắt đầu với đỉnh B và đỉnh F.
Câu 2:
Bản đồ giao thông kết nối 8 địa điểm nổi tiếng được mô tả như đồ thị G, (Hình 1). Theo em, có tồn tại một hành trình đi từ địa điểm D đến địa điểm G sao cho phải đi qua ít địa điểm trung gian nhất không? Chỉ ra hành trình đó.
Câu 3:
Hãy cho biết thứ tự duyệt các đỉnh với phương pháp duyệt đồ thị theo chiều rộng xuất phát từ đỉnh X của đồ thị G, ở Hình 2.
Câu 4:
Từ đồ thị G1 trong Hình 1. Hãy thực hiện yêu cầu sau:
a. Dùng thuật toán duyệt đồ thị theo chiều rộng để tìm đường đi ngắn nhất từ đỉnh C đến tất cả các đỉnh của đồ thị.
b. Từ câu a, mô tả cách duyệt cây theo chiều rộng bắt đầu từ đỉnh C.
Câu 5:
Cho hai đồ thị G3 (Hình 3) và G4 (Hình 4). Dùng thuật toán duyệt đồ thị theo chiều rộng để
thực hiện hai yêu cầu sau:
- Liệt kê thứ tự duyệt các đỉnh của đồ thị G3 xuất phát từ đỉnh A.
- Cho biết đường đi từ đỉnh F đến đỉnh J trong đồ thị G4 ?
Gọi 084 283 45 85
Hỗ trợ đăng ký khóa học tại Vietjack
về câu hỏi!