Kiểm tra tính liên thông của đơn đồ thị có hướng Trong đơn đồ thị có hướng, người ta thường quan tâm đến tính liên thông...

Để 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. Hướng dẫn gợi ý các bước của thuật toán:

Thuật toán Kosaraju

1. 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.

2. Đả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.

3. 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.

Cài đặt chi tiết bằng 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

Chú thích cài đặt:

1. dfs: Hàm DFS để duyệt đồ thị và lưu thứ tự hoàn thành các đỉnh.

2. reverse_graph: Hàm để tạo đồ thị đảo ngược.

3. fill_order: Hàm để chạy DFS trên đồ thị ban đầu và lưu thứ tự hoàn thành trong stack.

4. get_sccs: Hàm để chạy DFS trên đồ thị đảo ngược và tìm các thành phần liên thông mạnh.

5. kosaraju: Hàm chính để kiểm tra tính liên thông mạnh của đồ thị sử dụng các hàm trên.