om an co ng .c THUẬT TOÁN ỨNG DỤNG cu u du on g th Tarjan DFS algorithm for finding Bridges and Articulation Points Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn 1 Duyệt theo chiều sâu om  Cây DFS .c  DFS xuất phát từ một đỉnh cho phép thăm các đỉnh con co an  Cấu trúc dữ liệu duy trì ng cháu của nó trên cây DFS th  num[v]: thời điểm đỉnh v được thăm du on g  low[v]: giá trị num nhỏ nhất của các đỉnh x sao cho có cu u cạnh ngược (u,x) với u là 1 đỉnh con cháu nào đó của v 2 om DFS(6) .c 6 ng 1 co 4 th an 3 du on g 2 cu u 8 5 9 7 3 DFS(6) om num[6] = 1, low[6] = 1 cu u du on g th an co ng .c 6 4 DFS(6) om num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 .c 6 cu u du on g th an co ng 1 5 DFS(6) om num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 num[3] = 3, low[3] = 3 .c 6 co ng 1 cu u du on g th an 3 6 DFS(6) om num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 .c 6 co ng 1 th an 3 cu u du on g 2 7 DFS(6) om co ng 1 th an 3 cu u du on g 2 8 num[6] = 1, low[6] = 1 num[1] = 2, low[[1] = 2 num[3] = 3, low[3] = 3 num[2] = 4, low[2] = 4 num[8] = 5, low[8] = 5 .c 6 8 https://fb.com/tailieudie

阅读全文