Strongly connected component là gì?

Thành phần liên thông mạnh (strongly connected component) là phần của đồ thị có hướng (directed graph) trong đó có một đường đi (path) từ mỗi đỉnh (vertex) đến một đỉnh khác. Nó chỉ có thể áp dụng trên một đồ thị có hướng.

Ví dụ chúng ta có đồ thị dưới đây:

Các thành phần liên thông mạnh (strongly connected component) của đồ thị trên là:

Bạn có thể quan sát thấy rằng trong thành phần liên thông mạnh (strongly connected component) đầu tiên, mọi đỉnh đều có thể đến đỉnh khác thông qua đường đi có hướng (directed path).

Các thành phần này có thể được tìm thấy bằng thuật toán Kosaraju (Kosaraju's Algorithm).