Wikipedia

Khác biệt giữa bản sửa đổi của “Thuật toán tìm thành phần liên thông mạnh của Tarjan”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
Huynl (thảo luận | đóng góp)
494 sửa đổi
Huynl (thảo luận | đóng góp)
494 sửa đổi
nKhông có tóm lược sửa đổi
Dòng 1:
[[File:Tarjan's Algorithm Animation.gif|thumb|Tarjan's Algorithm Animation]]
'''Thuật Toán Tarjan''' (được đặt theo tên của người tìm ra nó - Robert Tarjan<ref>{{citation|first=R. E.|last=Tarjan|authorlink=Robert Tarjan|title=Depth-first search and linear graph algorithms|journal=[[SIAM Journal on Computing]]|volume=1|year=1972|issue=2|pages=146–160|doi=10.1137/0201010}}</ref>)và đượclà ứngmột dụngthuật toán trong [[Lý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ù đã tồn tại trước đó nhưng nhưng nó có thể được xem như là phiên bản cải tiến của [[thuật toán Kosaraju]] và cũng có thể so sánh về hiệu suất trong việc tìm kiếm thành phần liên thông mạnh.
==Tổng Quan==
*Đầu vào của thuật toán là [[đồ thị có hướng]], và tạo ra một vùng gồm 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 một thành phần liên thông mạnh đơn lẻ, ngay cả khi nó là một đỉnh xuất hiện trong thành phần liên thông mạnh của chính nó (như là trường hợp các bộ phận cây của đồ thị, cũng như bất kỳ đỉnh không có đỉnh kề hoặc không có đỉnh trước nó).
Lấy từ “https://vi.wikipedia.org/wiki/Thuật_toán_tìm_thành_phần_liên_thông_mạnh_của_Tarjan”