Thuật_toán tìm thành_phần liên_thông mạnh của Tarjan_Thuật_Toán_Tarjan được đặt theo tên của người tìm ra nó Robert_Tarjan 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 BULLET 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 BULLET Ý_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 tuỳ_ý 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 BULLET 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 BULLET Đ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 BULLET Để 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 BULLET 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 BULLET 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 đó BULLET 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 BULLET Độ 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 tuỳ_thuộc theo số_lượng các cạnh có trong đồ_thị G tức_là formula _ 1 BULLET 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 BULLET 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ô Xem thêm BULLET Description of Tarjan s Algorithm_BULLET_Implementation of Tarjan s Algorithm in NET BULLET Implementation of Tarjan s Algorithm in NET GitHub_BULLET_Implementation of Tarjan s Algorithm in PHP BULLET Another implementation of Tarjan s Algorithm in Python_BULLET_Implementation of Tarjan s Algorithm in Javascript
Thuật_toán tìm thành_phần liên_thông mạnh của Tarjan