Thuật toán tìm thành phần liên thông mạnh của Tarjan

Tarjan's Algorithm Animation

Thuật Toán Tarjan (được đặt theo tên của người tìm ra nó - Robert Tarjan^[1]) là một thuật toán trong lý thuyết đồ thị dùng để tìm thành phần liên thông mạnh trong một đồ thị. Mặc dù được tìm ra trước, nhưng nó có thể được xem như là phiên bản cải tiến của thuật toán Kosaraju.

Tổng quan

• Dữ liệu vào của thuật toán là một đồ thị có hướng, và kết quả của thuật toán là danh sách các đỉnh bên trong các thành phần liên thông mạnh của đồ thị đó. Mỗi đỉnh của đồ thị xuất hiện trong đúng một thành phần liên thông mạnh. Nếu một đỉnh không thuộc một chu trình có hướng nào thì nó nằm trong thành phần liên thông mạnh riêng của chính nó: chẳng hạn như đỉnh có bậc ra và bậc vào bằng 0, hay các đỉnh của một đồ thị có hướng không có chu trình.
• Ý tưởng cơ bản của thuật toán này là: tìm kiếm theo chiều sâu bắt đầu từ một đỉnh tùy ý (và sau đó tìm kiếm sâu dần trên bất kỳ các đỉnh nào chưa được xét). Việc tìm kiếm sẽ không xét đến bất kỳ đỉnh nào đã được xét trước đó. Các thành phần liên thông mạnh tạo nên các cây con của cây tìm kiếm, gốc của những cây con đó chính là gốc của các thành phần liên thông mạnh.
• Các đỉnh được đưa vào một ngăn xếp theo thứ tự mà chúng đã được xét. Khi việc tìm kiếm trả về một cây con, các đỉnh được lấy ra khỏi ngăn xếp và được xác định xem liệu mỗi đỉnh được lấy ra có phải là gốc của một thành phần liên thông mạnh hay không. Nếu một đỉnh đã được xác định là gốc của một thành phần liên thông mạnh thì nó và tất cả các đỉnh được lấy ra trước đó hình thành nên thành phần liên thông mạnh.

Các thuộc tính cơ bản

• Điểm mấu chốt của thuật toán chính là việc xác định một đỉnh có phải là gốc của một thành phần liên thông mạnh hay không. Đỉnh gốc đơn giản là đỉnh đầu tiên của thành phần liên thông mạnh được tìm thấy trong suốt quá trình tìm kiếm theo chiều sâu. Khi một đỉnh đã được xác định là đỉnh gốc, sau khi thăm xong đỉnh đó, tất cả các đỉnh nằm trong ngăn xếp từ gốc trở lên tạo thành một thành phần liên thông mạnh hoàn chỉnh.
• Để tìm đỉnh gốc, mỗi đỉnh v được gán cho một chỉ số tìm kiếm là v.index, trong đó chỉ số các đỉnh được đánh liên tục theo thứ tự mà chúng được tìm thấy. Ngoài ra, mỗi nút cũng lưu trữ giá trị v.lowlink bằng với chỉ số nhỏ nhất của các đỉnh có thể đến được từ v, kể cả chính v. Giá trị v.lowlink luôn luôn nhỏ hơn hoặc bằng v.index. Do đó v là gốc của một thành phần liên thông mạnh khi và chỉ khi v.lowlink = v.index. Giá trị v.lowlink được tính trong quá trình tìm kiếm theo chiều sâu.

Mã giả thuật toán

Dữ liệu vào: đồ thị G = (V, E)
Dữ liệu ra: các thành phần liên thông mạnh (các tập hợp các đỉnh)
 index:= 0
 S:= empty
 for mỗi đỉnh v trong tập V do
   if (v.index không xác định) then
     strongconnect(v)
   end if
 repeat
 Hàm strongconnect(v)
   //Thiết lập chỉ số chiều sâu cho v sao cho chỉ số không sử dụng là nhỏ nhất
   v.index:= index
   v.lowlink:= index
   index:= index + 1
   S.push(v)
   // Xem đỉnh kế của v
   for mỗi (v, w) trong E do
     if (w.index không xác định) then
       // Đỉnh kế w chưa được viếng thăm; đệ quy thăm nó
       strongconnect(w)
       v.lowlink:= min(v.lowlink, w.lowlink)
     else if (w is in S) then
       // Đỉnh kế w nằm trong ngăn xếp S và do đó nằm trong thành phần liên thông mạnh hiện tại
       v.lowlink:= min(v.lowlink, w.index)
     end if
   repeat
   // Nếu v là nút gốc, lấy ra khỏi ngăn xếp và tạo ra một thành phần liên thông mạnh
   if (v.lowlink = v.index) then
     bắt đầu một thành phần liên thông mạnh
     repeat
       w:= S.pop()
       thêm w vào thành phân liên mạnh hiện tại
     until (w = v)
     xuất ra thành phần liên thông mạnh hiện tại
   end if
 end function

• Biến index lưu số lần viếng thăm trong thuật toán tìm kiếm theo chiều sâu. S là ngăn xếp chứa các đỉnh,được khởi tạo ban đầu là một ngăn xếp rỗng và dung để lưu lại quá trình của những nút đã xét nhưng chưa hoàn tất việc tạo nên một thành phần liên thông mạnh.Lưu ý, đây không phải là thuật toán tìm kiếm theo chiều sâu trên ngăn xếp theo cách thông thường, bởi vì các đỉnh không được lấy ra giống như việc trả về kết quả tìm kiếm trên cây mà chúng chỉ được lấy ra khi toàn bộ thành phần liên thông mạnh được tìm thấy.
• Vòng lặp ngoài thực hiện tìm kiếm lần lượt tất cả những đỉnh chưa được xét đến trước đó, để đảm bảo rằng những đỉnh không đến được từ đỉnh đầu tiên vẫn được xét. Hàm strongconnect thực hiện tìm kiếm theo chiều sâu từ một đỉnh v trên đồ thị, tìm tất cả các đỉnh đến được từ v, và trả về tất cả các thành phần liên thông mạnh của đồ thị con đó.
• Khi mỗi đỉnh kết thúc việc tìm kiếm, nếu lowlink có giá trị bằng index thì đỉnh đó chính là đỉnh gốc của một thành phần liên thông mạnh - được hình từ bởi tất cả các đỉnh ở phía trước nó trong ngăn xếp. Thuật toán sẽ lấy ra tất cả các đỉnh có trong ngăn xếp và bao gồm đỉnh hiện tại, và trình bày tất các đỉnh như một thành phần liên thông mạnh.

Nhận xét

• Độ phức tạp: thủ tục Tarjan được gọi một lần cho mỗi cạnh và mỗi cạnh được xét qua nhiều nhất là hai lần. Chi phí thời gian của thuật toán là tuyến tính tùy thuộc theo số lượng các cạnh có trong đồ thị G tức là:${\displaystyle O(|V|+|E|)}$.
• Việc kiểm tra xem w có nằm trong ngăn xếp hay không được hoàn tất trong một khoảng thời gian hằng số. Một cách thực hiện việc này là với mỗi đỉnh, lưu một biến logic việc nó có nằm trong ngăn xếp hay không.
• Một ưu điểm của thuật toán là không có thành phần liên thông mạnh được xác định trước khi bất kỳ đỉnh kế của nó được xác định. Do đó, thứ tự của các thành phần liên thông mạnh đã được tìm thấy tạo thành nghịch đảo của một thứ tự sắp xếp tô pô.^[2]

Tham khảo

1. Tarjan, R. E. (1972), “Depth-first search and linear graph algorithms”, SIAM Journal on Computing, 1 (2): 146–160, doi:10.1137/0201010
2. Harrison, Paul. “Robust topological sorting and Tarjan's algorithm in Python”. Truy cập ngày 9 tháng 2 năm 2011.

Xem thêm

• Description of Tarjan's Algorithm
• Implementation of Tarjan's Algorithm in.NET
• Implementation of Tarjan's Algorithm in.NET (GitHub)
• Implementation of Tarjan's Algorithm in PHP
• Another implementation of Tarjan's Algorithm in Python
• Implementation of Tarjan's Algorithm in Javascript