Thuật toán Kosaraju

Trong khoa học máy tính, thuật toán Kosaraju-Sharir là một thuật toán tìm thành phần liên thông mạnh trong đồ thị có hướng. Theo Aho, Hopcroft và Ullman^[1], thuật toán này xuất hiện trong một bài báo chưa được công bố năm 1978 của S. Rao Kosaraju và Micha Sharir. Thuật toán sử dụng tính chất sau: trong đồ thị chuyển vị (đồ thị trong đó mọi cung được đảo ngược so với đồ thị ban đầu), các thành phần liên thông mạnh là không đổi so với đồ thị ban đầu.

Thuật toán Kosaraju-Sharir hoạt động như sau:

• Cho trước G là một đồ thị có hướng và một ngăn xếp rỗng S.
• Chừng nào S còn chưa chứa tất cả các đỉnh trong G:
  • Chọn một đỉnh v bất kì không nằm trong S. Thực hiện tìm kiếm theo chiều sâu bắt đầu từ v. Mỗi lần thuật toán tìm kiếm kết thúc việc tìm đường từ một đỉnh u, chèn u vào S.
• Đảo ngược tất cả các cung của đồ thị để có đồ thị chuyển vị
• Chừng nào S còn khác rỗng:
  • Lấy ra phần tử trên cùng v của S. Thực hiện tìm kiếm theo chiều sâu từ v trong đồ thị chuyển vị. Tập hợp các đỉnh được thăm chính là thành phần liên thông mạnh chứa v. Ghi nhận các đỉnh này và xóa chúng khỏi đồ thị và ngăn xếp S.

Độ phức tạp tính toán

Giả sử đồ thị được biểu diễn dưới dạng danh sách kề, thuật toán Kosaraju-Sharir duyệt qua toàn bộ đồ thị hai lần, do đó có độ phức tạp tính toán tuyến tính Θ(V+E). Độ phức tạp này là tối ưu bởi mọi thuật toán đều phải xem xét tất cả các đỉnh và cung của đồ thị. Thuật toán này vô cùng đơn giản nhưng trong thực tế không hiệu quả bằng các thuật toán của Tarjan và Gabow, do chúng chỉ duyệt qua đồ thị đúng một lần.

Nếu đồ thị được biểu diễn dưới dạng ma trận kề, thuật toán chạy trong thời gian Ο(V²)

Ghi chú

1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman (1983). Data Structures and Algorithms. Addison-Wesley.