Viết chương trình đếm số nước liên minh với nước đã cho trang 63 Chuyên đề Tin học 12

Giải Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng - Chân trời sáng tạo

Vận dụng trang 63 Chuyên đề Tin học 12: Viế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.

Lời giả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()

Lời giải bài tập Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng hay, chi tiết khác:

• Khởi động trang 59 Chuyên đề Tin học 12: Bản đồ giao thông kết nối 8 địa điểm nổi tiếng được mô tả như đồ thị G ....

• Câu hỏi trang 61 Chuyên đề Tin học 12: 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 ....

• Câu hỏi trang 62 Chuyên đề Tin học 12: Từ đồ thị G1 trong Hình 1. Hãy thực hiện yêu cầu sau ....

• Luyện tập trang 62 Chuyên đề Tin học 12: Cho hai đồ thị G3 (Hình 3) và G4 (Hình 4) ....

• Thực hành trang 62 Chuyên đề Tin học 12: Chương trình dưới đây duyệt đồ thị G3 (Hình 3) bắt đầu từ đỉnh B và đỉnh F ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Chân trời sáng tạo hay, chi tiết khác:

• Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin 12 Bài 3.1: Các khái niệm cơ bản của đồ thị

• Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị

• Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu

• Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---