Trong bài này, chúng ta sẽ tìm hiểu thuật toán Tarjan tìm thành phần liên thông mạnh của một đồ thị có hướng. Trước đây mình có một bài về thuật toán Kosaraju cho bài toán này. Ưu điểm của thuật toán Kosaraju là dễ hiểu hơn thuật toán Tarjan. Tuy nhiên, thuật toán Kosaraju chậm hơn so với thuật toán Tarjan do nó duyệt qua đồ thị hai lần, trong khi thuật toán Tarjan chỉ duyệt qua đồ thị một lần. Ngoài ra, ta có thể dễ dàng sửa đổi thuật toán Tarjan để áp dụng cho bài toán tìm các thành phần song liên thông (biconnected components) của đồ thị vô hướng (bài tập 2).
Trước khi đi sâu vào chi tiết, mình khuyến khích bạn đọc xem lại bài giới thiệu về đô thi và bài ứng dụng DFS trong sắp xếp topo. Bài viết này của mình ít nhiều giống bài viết trên wikipedia. Khái niệm thế nào là một thành phần bạn đọc xem tại bài thuật toán Kosaraju; mình sẽ không nhắc lại khái niệm này ở đây.
Tư tưởng thuật toán Tarjan
Gọi $G(V,E)$ là đồ thị (có hướng) đầu vào. Gọi $F$ là một rừng (forest) sau khi áp dụng DFS trên $G$. Gọi $C$ là một thành phần liên thông mạnh (nào đó) của $G$. Từ định nghĩ của thành phần liên thông mạnh, ta có:
Observation 1 cho ta biết đỉnh của cùng một thành phần liên thông mạnh không thể nằm trên 2 cây khác nhau của $F$. Do đó, ta có thể liệt kê các thành phần liên thông mạnh của $G$ băng cách lần lượt xét mỗi cây của $F$.
Gọi $T$ là một cây DFS của $G(V,E)$ có gốc tại nút $r$. Giả sử $C$ là một thành phần liên thông mạnh có các đỉnh thuộc $T$. Đỉnh $v$ được gọi là gốc của $C$ nếu $v$ là nút gần gốc $r$ nhất trong $C$, i.e, $v$ được thăm sớm nhất trong số các đỉnh của $C$ trong quá trình thực hiện thăm DFS. Từ định nghĩa của thành phần liên thông mạnh, ta có:
Để phát hiện thành phần liên thông mạnh $C$, đầu tiên ta sẽ tìm gốc $v$ của nó. Đâu là sự khác biệt của $v$ so với các nút khác cùng nằm trong $C$? Vì $v$ là đỉnh được thăm sớm nhất trong quá trình DFS, ta có:
Nếu bằng cách nào đó, trong quá trình duyệt đồ thị, ta đánh dấu được các đỉnh $u$ có đường đi tới ít nhất một đỉnh $w$ đã được thăm trước $u$ và nằm trong cùng một thành phần liên thông mạnh với $u$ thì ít nhất ta có thể phát hiện được các đỉnh gốc của các thành phần liên thông mạnh. Để minh họa ý tưởng, trước hết ta xét trường hợp đặc biệt khi đồ thị không có chung chéo.
TH đồ thị không có cung chéo.
Nhắc lại, trong bài sắp xếp topo, ta đã phân loại các cung của $G$ ra 4 loại sau khi thực hiện DFS: cung của cây DFS (tree arc), cung ngược (back arc), cung xuôi (forward arc) và cung chéo (cross arc).
Ta sẽ sử dụng DFS để đánh dấu các đỉnh không phải gốc. Khi thực hiện DFS, mỗi lần ta thăm một đỉnh mới $u$, ta gán cho nó một biến thời gian $I[u]$ đánh dấu thời điểm mà $u$ được thăm. ($I[r] = 0$ với $r$ là gốc của cây $T$.) Ta sẽ coi $I[u]$ như một định danh (id) của đỉnh $u$. Gọi $A[u]$ là định danh của một đỉnh $w$ (bất kì) đã được thăm trước $u$, cùng nằm trong một thành phần liên thông mạnh với $u$ và tồn tại một đường đi có hướng từ $u$ tới $w$. Ban đầu ta gán $A[u]= I[u]$ và ta sẽ cập nhật lại $A[u]$ trong quá trình thăm DFS. Nếu sau khi thăm DFS, $A[u] = I[u]$ thì ta biết rằng $u$ là gốc của một thành phần liên thông mạnh chứa $u$. Giả mã như sau:
mark every vertex in $V$ unvisited
$time \leftarrow -1$
for each unvisited vertex $v \in V$
MarkRoot($G,v,time$)
for each vertex $v \in V$
if $I[v] = A[v]$
print $v$ is a root
mark $u$ visited
$time\leftarrow time +1$
$I[u] \leftarrow time$
$A[u] \leftarrow I[v]$
for each $(u\rightarrow v) \in E$
if $v$ is unvisited
MarkRoot($G,v,time$)
$A[u] \leftarrow \min(A[u], A[v])$
Chứng minh tính đúng đắn của thủ tục FindAllRoots ta coi như bài tập cho bạn đọc. Gợi ý: chứng minh của bạn phải sử dụng tính chất đồ thị không có cung chéo. Nếu đồ thị có cung chéo thì thủ tục trên không còn đúng nữa, như sẽ chỉ ra dưới đây. Mình khuyến khích bạn đọc tự tìm phản ví dụ trước khi đọc tiếp.
TH đồ thị có cung chéo
Nhắc lại, cung chéo là các cung $(u \rightarrow v)$ trong đó, $v$ được thăm trước $u$ nhưng không phải là tổ tiên (ancestor) của $u$. Xét ví dụ trong Figure 1 dưới đây:
Figure 1: Các cung màu đỏ là các cung của cây DFS. Cung màu xanh là cung chéo (duy nhất) của đồ thị. Mỗi đỉnh được đánh dấu bằng một cặp $[I[u], A[u]]$ trong đó $I[u]$ là định danh của $u$ và $A[u]$ là giá trị thu được sau khi áp dụng thủ tục MarkRoot. Để ý vào đỉnh được tô đậm $e$. Đỉnh này có $I[e]$ < $A[e]$ nhưng nó lại là gốc của thành phần liên thông mạnh $\{e,f,g\}$.
Tổng quát hóa lên, thuật toán cập nhật MarkRoot sẽ sai nếu như ta gặp một cung chéo $u \rightarrow w$ mà $w$ lại không nằm trong cùng một thành phần liên thông mạnh với $u$. Tuy nhiên, trong trường hợp này, theo Observation 2, thành phần liên thông mạnh chứa $w$ đã được thăm xong trong quá trình DFS trước khi ta thăm $u$. Trở lại ví dụ trong Figure 1, giá trị $A[e]$ bị sai vì sự xuất hiện của cung chéo $(e \rightarrow d)$, trong khi $d$ được thăm trước $e$ và không nằm trong cùng một thành phần liên thông mạnh với $e$.
Nếu bằng cách nào đó, mỗi khi thăm xong một thành phần liên thông mạnh mà ta có thể "xóa" nó ra khỏi đồ thị thì thủ tục MarkRoot vẫn đúng. Đó là điểm chính trong ý tưởng của Tarjan.
Trong quá trình thăm, Tarjan sử dụng thêm một cấu trúc ngăn xếp $S$. Khi thăm mỗi đỉnh, Tarjan sẽ đẩy đỉnh đó vào $S$. Mỗi khi thăm xong các đỉnh của một thành phần liên thông mạnh $C$, Tarjan sẽ xóa các đỉnh của $C$ ra khỏi $S$. Việc xóa ra khỏi $S$ sẽ tương đương với việc "đánh dấu" $C$ đã bị xóa ra khỏi đồ thị.
Thuật toán Tarjan
Giả mã của thuật toán Tarjan như sau:
mark every vertex in $V$ unvisited
$time \leftarrow -1$
Stack $S \leftarrow \emptyset$
for each unvisited vertex $v \in V$
TarjanMarkRoot($G,v,time, S$)
mark $u$ visited
$time\leftarrow time +1$
$I[u] \leftarrow time$
$A[u] \leftarrow I[v]$
Push$(S,u)$
mark $u$ is in $S$
for each $(u\rightarrow v) \in E$
if $v$ is unvisited
TarjanMarkRoot($G,v,time, S$)
if $v$ is in $S$
$A[u] \leftarrow \min(A[u], A[v])$
if $A[u] = I[u]$
print $u$ is the root of a strongly connected component
while Peek$(S) \not= u$
$w \leftarrow $Pop$(S)$
print $w$
mark $w$ deleted from $S$
print Pop$(S)$
mark $u$ deleted from $S$
Code C:
to-do
Phần bôi đỏ là sự thay đổi chính so với thủ tục tìm gốc của các thành phần liên thông mạnh khi không có cung chéo. Thủ tục Push$(S,u)$, Peek$(S)$ và Pop$(S)$ lần lượt là thủ tục đẩy một đỉnh $u$ vào ngăn xếp, thủ tục lấy giá trị của phần tử trên đầu ngăn xếp (mà không xóa khỏi ngăn xếp), và thủ tục xóa một đỉnh ra khỏi ngăn xếp.
Để chứng minh tính đúng đắn của thuật toán Tarjan, ta cần phải chứng minh 3 điều: (1) mỗi khi một thành phần liên thông mạnh được DFS thăm xong thì đều bị xóa ra khỏi ngăn xếp, (2) nếu $v$ là gốc của một thành phần liên thông mạnh khi và chỉ khi $A[v] = I[v]$ và (3) một đỉnh chỉ bị xóa khỏi ngăn xếp khi thành phần liên thông mạnh chứa nó đã được thăm xong. Tất cả đều có thể chứng minh bằng quy nạp, và mình coi đó như bài tập cho bạn đọc.
Điều (2) có thể suy ra được từ điều (1), phỏng theo lập luận như trong trường hợp không có cung chéo. Điều (2) và (3) sẽ đảm bảo mỗi khi ta phát hiện được điểm gốc $v$ thì toàn bộ phần của ngăn xếp từ đầu cho đến đỉnh $v$ đều thuộc thành phần liên thông mạnh gốc tại $v$.
Tham khảo
[1] R. Tarjan. Depth-first Search and Linear Graph Algorithms. SIAM Journal on Computing 1.2 (1972): 146-160.
Bài tập
Bài 1: Áp dụng thuật toán Tarjan cho đồ thị trong Figure 1, vẽ lại trạng thái của ngăn xếp $S$ trong mỗi bước đi của thuật toán.
Bài 2: Cho một đồ thị đơn, liên thông, vô hướng $G(V,E)$. Ta gọi $u \in V$ là một đỉnh khớp (cut vertex) nếu như $G\setminus \{u\}$ có ít nhất 2 thành phần liên thông. Ta gọi cạnh $e \in E$ là một cầu (bridge edge) nếu $G\setminus \{e\}$ có ít nhất 2 thành phần liên thông. Hãy thay đổi thuật toán Tarjan để liêt kê tất cả cầu và khớp của đồ thị $G(V,E)$ trong thời gian $O(V+E)$.
Recent Comments