Giải chuyên đề Tin 12 Cánh diều Bài 6: Dự án học tập: Tìm hiểu các vấn đề ứng dụng đồ thị có đáp án

Một dãy đỉnh a = i₀, i₁,..., i_s = b (a ≠ b) được gọi là đường đi từ đinh a tới đỉnh b nếu hai đỉnh liên tiếp trên đường đi có cạnh nối.

Trong cuộc sống chúng ta gặp rất nhiều bài toán liên quan đến tìm đường đi, dưới đây là một ví dụ cụ thể.

Có n sân bay được đánh số từ 0 đến n - 1, có m tuyến bay giữa các sân bay, tuyến thứ k sẽ bay từ sân bay i, sang sân bay j. cách di chuyển từ sân bay a tới sân bay b với số tuyến bay là ít nhất bằng cách biểu diễn đồ thị như sau:

a) Biểu diễn đồ thị: Sử dụng danh sách kề (adjacency list) để biểu diễn đồ thị có hướng. Mỗi đỉnh (sân bay) sẽ có một danh sách các đỉnh mà nó có cạnh nối tới (các sân bay có tuyến bay trực tiếp tới).

b) Thuật toán BFS:

- BFS là thuật toán tìm kiếm theo chiều rộng, rất hiệu quả trong việc tìm đường đi ngắn nhất trên đồ thị không trọng số.

- Khởi tạo một hàng đợi (queue) và đưa đỉnh bắt đầu aaa vào hàng đợi.

- Sử dụng một mảng để theo dõi các đỉnh đã được thăm và mảng này cũng lưu khoảng cách từ đỉnh aaa tới các đỉnh khác.

- Trong khi hàng đợi không rỗng, lấy đỉnh đầu hàng đợi ra và duyệt qua tất cả các đỉnh kề của nó. Nếu đỉnh kề chưa được thăm, đánh dấu nó đã được thăm và thêm nó vào hàng đợi.

c) Truy vết đường đi:

- Để truy vết đường đi từ bbb về aaa, chúng ta có thể sử dụng một mảng cha (parent array) để lưu đỉnh trước đó của mỗi đỉnh trong quá trình BFS.

- Khi tìm thấy đỉnh bbb, chúng ta có thể truy ngược lại từ bbb về aaa để xác định đường đi.

d) Chương trình Python:

python

Sao chép mã

from collections import deque

def shortest_path(n, edges, a, b):

   # Bước 1: Xây dựng đồ thị dưới dạng danh sách kề

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

   for edge in edges:

        i, j = edge

        graph[i].append(j)

   # Bước 2: BFS để tìm đường đi ngắn nhất

   queue = deque([a])

   visited = [False] * n

   distance = [-1] * n  # Khoảng cách từ a tới các đỉnh

   parent = [-1] * n  # Để truy vết đường đi

   visited[a] = True

   distance[a] = 0

   while queue:

        current = queue.popleft()

        for neighbor in graph[current]:

            if not visited[neighbor]:

                visited[neighbor] = True

                distance[neighbor] = distance[current] + 1

                parent[neighbor] = current

                queue.append(neighbor)

                if neighbor == b:

                    # Nếu đã tới đích, dừng BFS

                    queue.clear()

                    break

   # Bước 3: Truy vết đường đi từ b về a

   path = []

   if visited[b]:

        current = b

        while current != -1:

            path.append(current)

            current = parent[current]

        path.reverse()

   return path if path and path[0] == a else []

# Ví dụ sử dụng:

n = 5  # Số sân bay

edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]  # Các tuyến bay

a = 0  # Sân bay bắt đầu

b = 4  # Sân bay đích

print(shortest_path(n, edges, a, b))

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)

Trong đơn đồ thị có hướng, người ta thường quan tâm đến tính liên thông mạnh của đồ thị. Một đồ thị có hướng được gọi là liên thông mạnh nếu từ một đỉnh bất kì của đồ thị có thể đến được tất cả các đỉnh còn lại.

Các bài toán liên quan đến tính liên thông của đơn đồ thị có hướng cũng có nhiều ứng dụng như tính liên thông của đơn đồ thị vô hướng.

Muốn kiểm tra tính liên thông mạnh của một đồ thị có hướng, chúng ta cần đảm bảo rằng từ bất kỳ đỉnh nào cũng có thể đi đến tất cả các đỉnh khác. Điều này yêu cầu mỗi đỉnh có thể đạt tới tất cả các đỉnh khác thông qua các cung của đồ thị có một thuật toán hiệu quả để kiểm tra tính liên thông mạnh của đồ thị có hướng, đó là thuật toán Kosaraju. Các bước của thuật toán như sau:

* Thuật toán Kosaraju

- Chạy DFS từ tất cả các đỉnh và lưu thứ tự hoàn thành của các đỉnh: Duyệt đồ thị và sử dụng DFS để lưu trữ thứ tự hoàn thành của các đỉnh trong một stack.

- Đảo ngược đồ thị: Tạo một đồ thị mới với tất cả các cạnh đảo ngược so với đồ thị gốc.

- Chạy DFS trên đồ thị đảo ngược theo thứ tự hoàn thành: Sử dụng stack từ bước 1 để chạy DFS trên đồ thị đảo ngược, bắt đầu từ đỉnh cuối cùng trong stack. Mỗi lần chạy DFS, các đỉnh được duyệt sẽ tạo thành một thành phần liên thông mạnh. Nếu sau bước 3, chỉ có một thành phần liên thông mạnh duy nhất chứa tất cả các đỉnh, thì đồ thị gốc là liên thông mạnh.

* Chương trình Python:

def kosaraju(n, edges):

   # Bước 1: Xây dựng đồ thị và chạy DFS để có thứ tự hoàn thành

   def dfs(v, graph, visited, stack):

        visited[v] = True

        for neighbor in graph[v]:

            if not visited[neighbor]:

                dfs(neighbor, graph, visited, stack)

        stack.append(v)

   # Bước 2: Đảo ngược đồ thị

   def reverse_graph(n, edges):

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

        for u, v in edges:

            reversed_graph[v].append(u)

        return reversed_graph

   # Bước 3: Chạy DFS trên đồ thị đảo ngược theo thứ tự hoàn thành

   def fill_order(n, graph):

        visited = [False] * n

        stack = []

        for i in range(n):

            if not visited[i]:

                dfs(i, graph, visited, stack)

        return stack

   def get_sccs(n, reversed_graph, stack):

        visited = [False] * n

        sccs = []

        while stack:

            v = stack.pop()

            if not visited[v]:

                scc_stack = []

                dfs(v, reversed_graph, visited, scc_stack)

                sccs.append(scc_stack)

        return sccs

   # Xây dựng đồ thị

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

   for u, v in edges:

        graph[u].append(v)

   # Bước 1: Chạy DFS và lấy thứ tự hoàn thành

   stack = fill_order(n, graph)

   # Bước 2: Đảo ngược đồ thị

   reversed_graph = reverse_graph(n, edges)

   # Bước 3: Chạy DFS trên đồ thị đảo ngược theo thứ tự hoàn thành

   sccs = get_sccs(n, reversed_graph, stack)

   # Kiểm tra số lượng thành phần liên thông mạnh

   return len(sccs) == 1

# Ví dụ sử dụng

n = 5

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

print(kosaraju(n, edges))  # Kết quả: True, đồ thị liên thông mạnh