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”
Nội dung được xóa Nội dung được thêm vào
n AlphamaEditor, Excuted time: 00:00:05.1133296 |
|||
Dòng 1:
[[
'''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>) 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òng 51:
*Độ 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à:<math>O(|V|+|E|)</math>.
*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ô]].<ref>{{chú thích web|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|accessdate=ngày 9
==Tham khảo==
{{tham khảo}}
| |||