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
nKhông có tóm lược sửa đổi
Huynl (thảo luận | đóng góp)
494 sửa đổi
sửa chính tả
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>) 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ồntìm tạira 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 Quanquan==
*ĐầuDữ liệu vào của thuật toán là một [[đồ thị có hướng]], và tạokết raquả mộtcủa vùngthuật toán là danh gồmsá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. đơnNếu lẻ,một ngayđỉnh cảkhông khithuộc nómột làchu mộttrình đỉnhcó xuấthướng hiệnnào thì nó nằm trong thành phần liên thông mạnh riêng của chính nó: (nhưchẳng làhạn trườngnhư hợpđỉnh cáccó bộbậc phậnra câyvà củabậc đồvào thịbằng 0, cũnghay như bất kỳcác đỉnh khôngcủa cómột đỉnhđồ kềthị hoặccó hướng không có đỉnhchu trước nó)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à 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ộcthuộc Tínhtính Cơcơ Bảnbả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. Các khái niệm về "gốc" chỉ áp dụng cho thuật toán này(Trong thực tế, một thành phần liên thông mạnh không chứa đỉnh "gốc" đơn). Đỉnh gốc đơn giản là đỉnh đầu tiên của thành phần liên thông mạnh - cái mà đượ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 mộtkhi lầnthăm đệxong quyđỉnh của nó hoàn thà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ộtchỉ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 đượccũng gánlưu một v.lowlinktrữ giá trị tươngv.lowlink đươngbằng với chỉ số nhỏ nhất của mộtcác số nútđỉnh có thể truyđến cậpđược từ v, vàkể luôncả luônchính nhỏv. hơnGiá hoặc bằngtrị v.indexlowlink nếuluôn khôngluôn cónhỏ núthơn kháchoặc có thể truy cập từ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ảgiả Thuậtthuật Toántoán==
inputDữ liệu vào: đồ thị G = (V, E)
output:Dữ sốliệu lượngra: 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
Dòng 27:
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 stackngăn xếp S và do đó nằm trong SCCthà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 Stackngăn xếp và tạo ra một SCCthà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
Dòng 45:
end if
end function
*Biến index là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 từnglần đỉnhlượt mộttất -cả những đỉnh mà chưa được xét đến trước đó, vàđể đảm bảo rằng những đỉnh không liênđến kếtđược vớitừ đỉ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]] đơntừ lẻmột đỉnh v trên đồ thị, tìm tất cả các đỉnh kềđến đỉnhđược từ Vv, 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étxé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à:<math>O(|V|+|E|)</math>.
*TiếnViệc hànhkiểm thửtra nghiệm cho dùxem w có nằm ở vị trí bất kỳ trêntrong [[ngăn xếp]] cũnghay nênkhông được hoàn tất trong một khoảng thời gian cốhằng địnhsố. VíMột dụ:cách thực Bằnghiện việc kiểmnày tralà cờ được gán chovới mỗi đỉnh, giúplưu xácmột địnhbiến đượclogic vịviệc trínó củacó đỉnhnằm đótrong trên [[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 loạithứ topotự nghịch[[sắp đảoxếp tô DAGpô]].<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=9 February 2011}}</ref>
==Tham Khảokhảo==
{{tham khảo}}
==Xem Thêmthêm==
*[http://www.ics.uci.edu/~eppstein/161/960220.html#sca Description of Tarjan's Algorithm]
*[http://stackoverflow.com/questions/6643076/tarjan-cycle-detection-help-c#sca Implementation of Tarjan's Algorithm in .NET]
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”