Kiểm tra tính liên thông của đơn đồ thị vô hướng trang 73 Chuyên đề Tin học 12

Trang trước Trang sau

Vấn đề 2 trang 73 Chuyên đề Tin học 12: Kiểm tra tính liên thông của đơn đồ thị vô hướng

Một đơn đồ thị vô hướng được gọi là liên thông nếu hai đinh bất kì của đồ thị đều có đường đi tới nhau.

Bài toán kiểm tra tính liên thông của đơn đồ thị vô hướng xuất hiện nhiều trong nghiên cứu lí thuyết cũng như ứng dụng trong cuộc sống, sau đây là một ví dụ cụ thể:

Có địa điểm được đánh số từ 0 đến n - 1, có m tuyến xe buýt hai chiều giữa các địa điểm, tuyển thứ k sẽ di chuyển giữa hai địa điểm ik, và jk, Em hãy kiểm tra xem từ một địa điểm bất kì có thể tới được các địa điểm còn lại bằng cách chỉ sử dụng m tuyển xe buýt hay không.

Lời giải:

Sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) hoặc tìm kiếm theo chiều sâu (DFS):

- Bước 1: Biểu diễn đồ thị

Chúng ta sẽ sử dụng danh sách kề (adjacency list) để biểu diễn đồ thị. Giả sử đồ thị có n đỉnh và m cạnh.

def create_adjacency_list(n, edges):

   adjacency_list = [[] for _ in range(n)]

   for (u, v) in edges:

        adjacency_list[u].append(v)

        adjacency_list[v].append(u)

   return adjacency_list

- Bước 2: Sử dụng BFS hoặc DFS để kiểm tra tính liên thông

Chúng ta sẽ chọn một đỉnh làm điểm bắt đầu (ví dụ đỉnh 0) và sử dụng BFS hoặc DFS để tìm tất cả các đỉnh có thể đi đến từ đỉnh đó. Nếu tất cả n đỉnh đều được thăm, thì đồ thị là liên thông.

def bfs(start, adjacency_list, visited):

   queue = [start]

   visited[start] = True

   while queue:

        node = queue.pop(0)

        for neighbor in adjacency_list[node]:

            if not visited[neighbor]:

                visited[neighbor] = True

                queue.append(neighbor)

- Bước 3: Kiểm tra tất cả các đỉnh đã được thăm

Sau khi thực hiện BFS hoặc DFS, chúng ta kiểm tra xem tất cả các đỉnh đã được thăm hay chưa.

def is_connected(n, edges):

   if n == 0:

        return True  # Không có đỉnh nào, coi như liên thông

   adjacency_list = create_adjacency_list(n, edges)

   visited = [False] * n

   # Sử dụng BFS bắt đầu từ đỉnh 0

   bfs(0, adjacency_list, visited)

   # Kiểm tra xem tất cả các đỉnh đã được thăm chưa

   for v in visited:

        if not v:

            return False

   return True

Ví dụ:

Giả sử chúng ta có 5 địa điểm (đỉnh) và 4 tuyến xe buýt (cạnh):

n = 5

edges = [(0, 1), (1, 2), (2, 3), (3, 4)]

print(is_connected(n, edges)) 

# Kết quả: True, vì đồ thị này là liên thông

Giả sử chúng ta có 5 địa điểm và 3 tuyến xe buýt:

n = 5

edges = [(0, 1), (1, 2), (3, 4)]

print(is_connected(n, edges)) 

Vậy False, vì đồ thị này không liên thông (có 2 thành phần liên thông)

Lời giải bài tập Chuyên đề Tin 12 Bài 6: Dự án học tập: Tìm hiểu các vấn đề ứng dụng đồ thị hay, chi tiết khác:

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Cánh diều hay, chi tiết khác:

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

Trang trước Trang sau
Giải bài tập lớp 12 sách mới các môn học