Trong bài trước, chúng ta đã làm quen với thuật toán duyệt theo chiều sâu DFS trên đồ thị (vô hướng). Chúng ta cũng chưa có dịp để thảo luận về các ứng dụng của thuật toán DFS mặc dù đây là một thuật toán có rất nhiều ứng dụng trong thiết kế giải thuật. Trong phần này chúng ta sẽ làm quen với ứng dụng của DFS trong bài toán sắp xếp Topo (Topological Sort). Đồ thị trong bài này là đồ thị có hướng với biểu diễn mặc định là sử dụng danh sách kề. Để dễ phân biết, ta kí hiệu đồ thị có hướng là $G(V,\vec{E})$. Đồ thị vô hướng thu được từ $G(V,\vec{E})$ bằng cách bỏ qua hướng của cạnh ta sẽ kí hiệu là $G(V,E)$. Một số khái niệm khác ở bài trước chúng ta sẽ không nhắc lại ở đây nữa.
Phân loại cung theo DFS
Giả mã của thuật toán DFS cơ bản thăm đồ thị $G(V,\vec{E})$ như sau:
mark all vertices unvisited
for each vertex $v$
if $u$ is unvisited
RecursiveDFS($u$) [[$(*)$]]
mark $u$ visited
for all $(u \rightarrow v) \in \vec{E}$ and $v$ is unvisited.
RecursiveDFS($v$) [[$(**)$]]
Gọi $U = \{u_1,u_2,\ldots,u_k\}$ là các đỉnh được thăm ở dòng $(*)$. Một đỉnh $v$ được gọi là trong tầm với của $u$ (reachable from $u$) nếu tồn tại một đường đi có hướng từ $u$ tới $v$. Dễ thấy với mọi $v \in V \setminus U$, đỉnh $v$ nằm trong tầm với một trong các đỉnh của $U$.
Bây giờ ta muốn xem mỗi đỉnh $v \in V \setminus U$ nằm trong tầm với của đỉnh nào trong $U$. Một đỉnh $v$ có thể nằm trong tầm với của hai hay nhiều đỉnh khác nhau trong $U$, nhưng ở đây ta chỉ quan tâm để đỉnh đầu tiên trong $U$, i.e, đỉnh có chỉ số nhỏ nhất, mà $v$ nằm trong tầm với của đỉnh đó. Ngoài ra, nếu $v$ nằm trong tầm với của $u_i$, ta muốn in ra đường đi từ $u_i$ đến $v$. Ta gọi mỗi đỉnh $u_i$ là nguồn của $v$.
Để thu được thông tin đó, ta sẽ sửa đổi DFS một chút bằng cách thêm một vài mảng đánh dấu. Ta sử dụng mảng $L[1,2\ldots,n]$ trong đó $L[v] = u_i$ nếu $u_i$ là nguồn của $v$. Ban đầu khởi tạo $L[u_i] = u_i$ với mỗi $u_i \in U$. Để lưu vết đường đi từ $u_i$ đến $v$, ta sẽ lưu một mảng $P[1,2,\ldots,n]$ trong đó $P[v] = x$ nếu cung $(x \rightarrow v)$ nằm trong đường đi từ $u_i$ tới $v$. Hay nói cách khác, $x$ đứng ngay trước $v$ trong đường đi có hướng từ $u_i$ tới $v$. Ta gọi cung $(x \rightarrow v)$ là cung được thăm bởi DFS. Khi ta đã có mảng $P$ thì đường đi từ $v$ tới $u_i$ (viết theo thứ tự ngược) là:
$(v, P[v], P[P[v]], \ldots, P[\ldots P[v] \ldots] = u_i)$.
Thủ tục in ra đường đi từ $u_i$ tới $v$ theo thứ tự ngược (in thứ tự xuôi coi như bài tập cho bạn đọc):
while $v \not= P[v]$
print $v$
$v \leftarrow P[v]$
print $v$
Code C:
void print_reverse_path(int v, int *P){ while(v != P[v]){ printf("%d ",v); v = P[v]; } printf("%d\n",v); }
Giả mã của DFS sửa đổi:
mark all vertices unvisited
for each vertex $v$
if $u$ is unvisited
$P[u] \leftarrow \emptyset$
$L[u] \leftarrow u$
RecursiveDFS($u$) [[$(*)$]]
mark $u$ visited
for all $(u \rightarrow v) \in E$ and $v$ is unvisited.
$P[v] \leftarrow u$
$L[v] \leftarrow L[u]$
RecursiveDFS($v$) [[$(**)$]]
Code C:
#define UNVISITED 0 #define VISITING 1 #define VISITED 2 // the vertex list data structure, it is a linked list typedef struct vlist{ int v; // vertex v is adjacent to the index of the list struct vlist *next; }vlist; vlist **G; int n; // the number of veritces int m; // the number of edges int *L; int *P; // to trace the path between s and t int* mark; // an array to mark visited vertices void dfs_all(){ int u = 0; for(; u < n; u++){ if(mark[u] == UNVISITED){ P[u] = u; L[u] = u; recursive_dfs(u); } } } void recursive_dfs(int u){ printf("visiting %d\n",u); mark[u] = VISITED; // loop through neighbors of s vlist *runner = G[u]; int v; while(runner != NULL){ // examine all neighbors of s v = runner->v; if(mark[v] == UNVISITED) { // mark[v] == UNVISITED P[v] = u; L[v] = L[u]; recursive_dfs(v); } runner = runner->next; } mark[u] = VISITED; }
Ví dụ thực thi thủ tục trên trong hình dưới đây. Các cung màu đỏ là các cung được thăm bởi DFS. Nhìn vào hình vẽ ta thấy các cung này sẽ tạo thành một rừng (forest) gọi là rừng DFS (DFS forest), trong đó gốc của mỗi cây (đỉnh được tô màu) trong rừng là một đỉnh trong $U$. Ta sẽ chứng minh điều này một cách hình thức hơn trong Lemma 1.
Gọi $\vec{E_{dfs}}$ là tập các cung được thăm bởi DFS. Ta có:
Chứng minh: Ta sẽ chứng minh mỗi $\vec{T_i}$ là một cây có hướng gốc tại $u_i$. Việc chứng minh các đỉnh của $T_i$ đều đến được từ $u_i$ coi như bài tập cho bạn đọc. Từ thủ tục DFS ở trên, ta có nhận xét:
Nhận xét: Mỗi đỉnh $v \in V$, tồn tại duy nhất một đỉnh $u$ sao cho $P[v] = u$.
Xét cây vô hướng tương ứng $T_i$, giả sử $T_i$ có ít nhất một chu trình. Xét một chu trình $C$ (vô hướng) nào đó của $T_i$ có $\ell$ đỉnh. Gọi $v$ là một đỉnh của $C$ được thăm đầu tiên bởi DFS. Gọi $v=v_1,v_2,\ldots, v_\ell $ là thứ tự các đỉnh dọc theo $C$ sao cho $v$ kề với $v_\ell$. Do $v_1$ là đỉnh được thăm đầu tiên, $v_2$ được thăm sau $v_1$. Do các cạnh thăm bởi DFS đều có dạng $(P[v] \rightarrow v)$ và $P[v]$ là duy nhất, ta suy ra $P[v_2] = v_1$. Lập luận tương tự ta có:
$P[v_3] = v_2, \ldots, P[v_{i+1}] =v_i, \ldots, P[v_\ell] = v_{\ell-1}$
Do $v_\ell \in C$, ta dễ dàng suy ra $P[v] = v_\ell$ hoặc $P[v_\ell] = v$. Do $P[v_\ell] = v_{\ell-1}$ và $v_{\ell-1} \not= v$, ta có $P[v] = v_\ell$. Nhưng điều này trái với giả thiết $v$ là đỉnh được thăm đầu tiên của $C$. Do đó, chu trình $C$ không tồn tại. Hay nói cách khác, $T_i$ là một cây.
Xét các cung được thăm và không được thăm bởi DFS, ta có 4 loại cung sau:
- Cung của cây DFS (tree arcs) là các cung thuộc $G(V, \vec{E_{dfs}})$. Các cung này được đánh dấu màu đỏ trong hình $(1)$ dưới đây.
- Cung xuôi (forward arcs) là các cung khác các cung của cây và có dạng $u \rightarrow v$ trong đó $u$ là tổ tiên của $v$ ($u$ gần gốc hơn $v$ và $v$ nằm trong tầm với của $u$). Các cung này được đánh dấu màu xanh lam trong hình $(2)$ dưới đây.
- Cung ngược (back arcs) là các cung có dạng $v \rightarrow u$ trong đó $u$ là tổ tiên của $v$. Các cung này được đánh dấu màu tím trong hình $(3)$ dưới đây.
- Cung chéo (cross arcs) là các cung có dạng $v \rightarrow u$ trong đó $u$ và $v$ thuộc hai nhánh khác nhau của cùng một cây hoặc thuộc hai cây khác nhau. Các cung này được đánh dấu màu xanh lá cây trong hình $(4)$ dưới đây.
Các cung của cây DFS khá là dễ phân bệt và đó chính là cung $(u\rightarrow v)$ trong đó $v$ là đỉnh được gọi ở dòng $(**)$ (trong giả mã có đoạn mã màu đỏ ở trên). Trong điều kiên ở vòng for ở thủ tục RecursiveDFSB, các cung $(u\rightarrow v)$ mà $v$ là visitted sẽ có thể là một trong 3 loại cung: chéo, ngược hoặc xuối. Do đó, chỉ với hai nhãn này thì ta chưa phân biết được cung ngược với các cung khác (bài này ta chưa cần phân biệt cung chéo và cung xuôi). Nhắc lại, cung ngược là cung từ một đỉnh $u$ tới một đỉnh tổ tiên của nó trong cùng một cây của rừng DFS.
Để phát hiện ra cung xuôi ta phải dùng thêm một nhãn nữa là nhãn visitting, bên cạnh hai nhãn là visitted và unvissited. Ý nghĩa các nhãn như sau:
- Unvisited: Ý nghĩa của nhãn này khá rõ ràng rồi. Đỉnh $x$ có nhãn unvisitted nếu $x$ chưa được thăm.
- Visitting: Đỉnh $x$ có nhãn visiting nếu như ta đang thăm các đỉnh con cháu của $x$ trong cây DFS.
- Visited: Đỉnh $x$ có nhãn visited nếu như ta đã thăm hết các con cháu của $x$.
Dựa vào định nghĩa của các nhãn, ta suy ra: khi đang thăm đỉnh $u$ (có nhãn visitting), nếu ta bắt gặp đỉnh $v$ mà:
- Đỉnh $v$ là unvisited thì $u \rightarrow v$ là cung của cây DFS.
- Đỉnh $v$ visitting thì ta biết $u$ là con cháu của $v$ vì ta vẫn đang thăm các đỉnh con cháu của $v$ trong cấy DFS. Do đó $u \rightarrow v$ là cung ngược.
- Đỉnh $v$ visited thì $u \rightarrow v$ là cung xuôi hoặc cung chéo.
Như vậy ta "gần như" đã phân loại được được các cạnh của DFS. Để phân biệt cung xuôi và cung chéo, ta cần sửa đổi DFS hơn nữa. Vấn đề này ta sẽ tìm hiểu trong bài sau. Giả mã như sau:
mark all vertices unvisited
for each vertex $v$
if $u$ is unvisited
RecursiveDFS($u$) [[$(*)$]]
mark $u$ visiting
for all $(u \rightarrow v) \in \vec{E}$
if $v$ is visiting
$(u\rightarrow v)$ is a back arc
if $v$ is visited
$(u\rightarrow v)$ is a cross arc or a forward arc.
if $v$ is unvisited
$(u\rightarrow v)$ is a tree arc.
RecursiveDFS($v$) [[$(**)$]]
mark $u$ visited
Code C:
#define UNVISITED 0 #define VISITING 1 #define VISITED 2 // the vertex list data structure, it is a linked list typedef struct vlist{ int v; // vertex v is adjacent to the index of the list struct vlist *next; }vlist; vlist **G; int n; // the number of veritces int m; // the number of edges int *L; int *P; // to trace the path between s and t int* mark; // an array to mark visited vertices void dfs_all(){ int u = 0; for(; u < n; u++){ if(mark[u] == UNVISITED){ P[u] = u; L[u] = u; recursive_dfs(u); } } } void recursive_dfs(int u){ printf("visiting %d\n",u); mark[u] = VISITING; // loop through neighbors of s vlist *runner = G[u]; int v; while(runner != NULL){ // examine all neighbors of s v = runner->v; if(mark[v] == VISITING){ printf("arc (%d->%d) is a back arc\n", u,v); } else if(mark[v] == VISITED){ printf("arc (%d->%d) is a cross arc or a forward arc\n", u,v); } else { // mark[v] == UNVISITED printf("arc (%d->%d) is a tree arc\n", u,v); P[v] = u; L[v] = L[u]; recursive_dfs(v); } runner = runner->next; } mark[u] = VISITED; }
DAG
Một đồ thị có hướng $G(V,\vec{E})$ được gọi là DAG (directed acyclic graph -- đồ thị có hướng và không có chu trình) nếu $G(V,\vec{E})$ không có chu trình có hướng. Ở đây ta nhấn mạnh cụm từ không có chu trình có hướng. Điều đó có nghĩa là đồ thị vô hướng tương ứng $G(V,E)$ vẫn có thể có chu trình. Đồ thị trong ví dụ ở trên không phải là DAG do đồ thị đó có chu trình $b \rightarrow c \rightarrow d \rightarrow b$. Đồ thị trong hình $(5)$ dưới đây là một DAG. Ta có bài toán sau:
Gọi $G(V,\overleftarrow{E})$ là đồ thị thu được bằng cách đảo ngược các cung của $G(V,\vec{E})$. Ta có nhận xét sau:
Đỉnh $s \in V$ của đồ thị $G(V,\vec{E})$ được gọi là một đỉnh phát (source vertex) nếu như không tồn tại $u$ sao cho $u\rightarrow s \in \vec{E}$. Nói cách khác, $s$ là phát nếu bậc tới (in-degree) của $s$ bằng $0$. Đỉnh $s \in V$ của đồ thị $G(V,\vec{E})$ được gọi là một đỉnh thu (sink vertex) nếu như không tồn tại $u$ sao cho $s\rightarrow u \in \vec{E}$. Hay nói cách khác, $s$ là đỉnh thu nếu bậc lui (out-degree) của $s$ bằng $0$. Ví dụ trong hình $(5)$ dưới đây, các đỉnh $a,d, k$ là các đỉnh phát, các đỉnh $c,g$ là các đỉnh thu.
Ta có bổ đề sau:
Chứng minh: Nhận xét đỉnh phát của $G(V, \overleftarrow{E})$ chính là đỉnh thu của $G(V, \vec{E})$. Do đó, dựa vào Fact 1, ta chỉ cần chứng minh $G(V,\vec{E})$ luôn có một đỉnh phát
Chọn một đỉnh $v \in V$ và đánh dấu đỉnh $v$. Gọi $u$ là đỉnh sao cho $u\rightarrow v \in \vec{E}$. Nếu $u$ không tồn tại thì $v$ là đỉnh thu, bổ đề là đúng. Nếu $u$ tồn tại, ta tiếp tục đánh dấu $u$ và lặp lại quá trình đánh dấu như vậy cho đến khi ta gặp một đỉnh $y$ là đỉnh thu hoặc tồn tại một đỉnh $x$ sao cho $x\rightarrow y \in \vec{E}$ và $x$ đã được đánh dấu. Trong trường hợp sau, ta sẽ tìm được một chu trình có hướng bao gồm các đỉnh đã đánh dấu, trái với giả thiết $G(V,\vec{E})$ là DAG.
Gọi $s_1,s_2,\ldots, s_k$ là tập các đỉnh nguồn của $G(V,\vec{E})$. Thêm vào một đỉnh $s$ và thêm $k$ cung $s\rightarrow s_i$. Gọi $G_s(V_s,\vec{E}_s)$ là đồ thị thu được. Dễ thấy:
Nhận xét: nếu $G(V,\vec{E})$ là DAG thì $G_s(V_s,\vec{E}_s)$ cũng là DAG và ngược lại.
Ngoài ra, nếu ta thực hiện DFS bắt đầu từ $s$, ta sẽ chỉ thu được duy nhất một cây DFS gốc tại $s$ (tại sao?). Ta có bổ đề sau:
Chứng minh: Chiều thuận của bổ đề khá dễ để chứng minh. Nếu cây DFS gốc tại $s$ có cung $u \rightarrow v$ là cung ngược, $u$ và $v$ đều có nhãn unvisiting. Do đó là cung ngược, $v$ sẽ là tổ tiền của $u$ trong cây DFS. Hay nói cách khác, có một đường đi $P(v\rightarrow u)$ từ $v$ đến $u$. Đường đi đó kết hợp với cạnh $u \rightarrow v$ sẽ tạo thành một chu trình có hướng. Do đó $G_s(V_s,\vec{E}_s)$ không phải là DAG.
Ta chứng minh chiều ngược lại bằng phản chứng. Giả sử $G$ không phải là DAG, gọi $C$ là một chu trình có hướng của $G$. Gọi $v$ là đỉnh đầu tiên của $C$ được thăm bởi DFS và $u \in C$ là đỉnh mà $(u\rightarrow v) \in C$. Đỉnh $v$ chỉ được đánh dấu là visited sau khi tất cả các đỉnh trong tầm với của $v$ (reachable from $$), trong đó có $u$, đã được đánh dấu là visited. Do đó, khi ta thăm $u$, đỉnh $v$ đang được đánh dấu là visiting. Như vậy, $u \rightarrow v$ là cung ngược, trái với giả thiết là cây DFS không có cung ngược.
Từ Lemma 3, ta có thể giải Problem 1 bằng cách thay đổi một chút thủ tục RecursiveDFSC như sau:
$S \leftarrow $ FindSources$(G(V,\vec{E})$ $\ll $ the set of sources $\gg$
mark all vertices unvisited
add a vertex $s$ to $G(V,\vec{E})$
for each all sink $s_i \in S$
add $s \rightarrow s_i$
DFSChecker($s$)
report $G(V,\vec{E})$ is DAG.
mark $u$ visiting
for all $(u \rightarrow v) \in \vec{E}$
if $v$ is visiting
report $(G,\vec{E})$ is non-DAG and exit
if $v$ is unvisited
DFSChecker($v$)
mark $u$ visited
Code C:
#define UNVISITED 0 #define VISITING 1 #define VISITED 2 // the vertex list data structure, it is a linked list typedef struct vlist{ int v; // vertex v is adjacent to the index of the list struct vlist *next; }vlist; vlist **G; // the graph int n; // the number of veritces int m; // the number of edges int* mark; // an array to mark visited vertices void dag_checker(){ vlist *S = find_sources(); mark = (int *)malloc((n+1)*sizeof(int)); memset(mark, UNVISITED, (n+1)*sizeof(int)); int s = n; // the new added vertex s while(S != NULL){ add_arc(s,S->v); S = S->next; } printf("checking dag graph.....\n"); dfs_checker(s); printf("The input graph is a DAG\n"); } void dfs_checker(int u){ printf("visiting %d\n",u); mark[u] = VISITING; // loop through neighbors of u vlist *runner = G[u]; int v; while(runner != NULL){ // examine all neighbors of s v = runner->v; if(mark[v] == VISITING){ printf("The input graph is non-dag\n"); exit(0); } else if(mark[v] == UNVISITED){ dfs_checker(v); } runner = runner->next; } mark[u] = VISITED; } // we use vlist as a linked list of sources vlist *find_sources(){ int *M = (int *)malloc(n*sizeof(int)); // array M to mark which vertex is not a source memset(M,0,n*sizeof(int)); // loop through all edges of G to find sources int u = 0; vlist *nbrRunner; for(; u < n; u++){ nbrRunner = G[u]; while(nbrRunner != NULL){ M[nbrRunner->v] = 1; // v is not a source nbrRunner = nbrRunner->next; } } vlist *head = NULL; // the head of the source list for( u = 0; u < n; u++){ if(M[u] == 0){ // u is a source vlist *node = malloc(sizeof(vlist)); node->v = u; node->next = head; head = node; } } return head; }
Phân tích thuật toán: Nếu biểu diễn đồ thị bằng danh sách kề, mỗi đỉnh $u$ có hai danh sách: một danh sách các đỉnh $v$ (gọi là các đỉnh tới) sao cho $(u\rightarrow v \in \vec{E})$ và một danh sách khác lưu các đỉnh $w$ (gọi là các đỉnh lui) sao cho $(w\rightarrow u) \in \vec{E}$ thì việc phát hiện các đỉnh phát (sink) có thể được thực hiện trong thời gian $O(n)$. Nếu ta chỉ lưu một danh sách là các đỉnh tới thì việc phát hiện nguồn có thể thực hiện trong thời gian $O(m)$ bằng cách duyệt qua các cung và đánh dấu các đỉnh cuối của mỗi cung. Các đỉnh không bị đánh dấu chính là các đỉnh nguồn.
Việc thêm đỉnh $s$ vào đồ thị cũng có thể được thực hiện trong thời gian $O(n)$. Thuật toán DFS có thời gian $O(n+m)$. Do đó thời gian của thuật toán DAGChecker là $O(n+m)$.
Remarks: Đỉnh $s$ thêm vào đồ thị để việc trình bày thuật toạn được đơn giản hơn. Khi thực thi thuật toán DAGChecker, ta không nhất thiết phải thêm vào đỉnh này.
Ngoài ra, dựa vào chứng minh của Lemma 3, ta có thể dễ dàng mở rộng thuật toán DAGChecker để in ra một chu trình có hướng trong trường hợp $G(V,\vec{E})$ không phải là DAG. Chi tiết coi như bài tập cho bạn đọc.
Sắp xếp Topo
Sắp xếp Topo của một đồ thị có hướng $G(V,\vec{E})$ là một cách sắp xếp các đỉnh trên một đường thẳng sao cho với mỗi cung $(u\rightarrow v) \in \vec{E}$, đỉnh $u$ nằm bên trái đỉnh $v$ trên đường thẳng đó. Ví dụ hình (6) dưới đây là một sắp xếp topo của đồ thị trong hình (5).
Từ định nghĩa của săp xếp Topo ta có thể dễ dàng thấy rằng nếu $G(V,\vec{E})$ có một sắp xếp Topo thì $G(V,\vec{E})$ không thể có một chu trình có hướng. Hay nói cách khác, $G(V,\vec{E})$ là một DAG. Ngược lại, cho một DAG $G(V,\vec{E})$, luôn tồn tại một sắp xếp Topo cho $G(V,\vec{E})$. Ta sẽ chứng minh điều này bằng cách thiết kế một giải thuật để tìm sắp xếp Topo đó. Ta có:
Ta có thể coi sắp xếp Topo giống như gán lại chỉ số trong tập $\{1,2,\ldots,n \}$ cho mỗi đỉnh sao cho với mỗi cung $(u\rightarrow v) \in \vec{E}$, đỉnh $u$ được gán chỉ số nhỏ hơn $v$. Để biểu diễn thứ tự của sắp xếp Topo, ta sẽ dùng một mảng $Ts[1,2,\ldots,n]$ trong đó nếu $Ts[u] = i, Ts[v] = j, (u\rightarrow v) \in \vec{E}$ thì $i < j$. Gọi $S = \{s_1,s_2,\ldots, s_k\}$ là tập các đỉnh nguồn của $G(V,\vec{E})$. Ta có:
Nhận xét: Ta có thể đổi chỗ các đỉnh trong tập $S$ trong một sắp xếp Topo của $G(V,\vec{E})$ mà thứ tự các đỉnh sau khi đổi chỗ vẫn là thứ tự của một sắp xếp Topo (khác) của $G(V,\vec{E})$.
Dựa vào nhận xét trên, ta có thể tìm một sắp xếp Topo của DAG $G(V,\vec{E})$ như sau: Mỗi lần ta phát hiện ra một đỉnh nguồn mới, ta sẽ đưa đỉnh đó vào vị trí còn trống đầu tiên của mảng $Ts$ và xóa đỉnh nguồn đó từ đồ thị. Ngoài ra, ta sẽ dùng một tập hợp $S$ để lưu trữ các đỉnh nguồn của đồ thị hiện tại. Thuật toán như sau:
$S \leftarrow$ all source vertices of $G(V,\vec{E})$
$i \leftarrow 1$
while $S \not= \emptyset$
$s \leftarrow $ a vertex from $S$
$Ts[s] \leftarrow i$
$i \leftarrow i+1$
delete $s$ from $G(V,\vec{E})$
for each out-neighbor $v$ of $s$ in $G(V,\vec{E})$ [[$(s\rightarrow v) \in \vec{E}$]]
if $s$ is the only in-neighbor of $v$ [[$v$ become a sink]]
put $v$ to $S$
output $Ts[1,2,\ldots,n]$
Trong thực tế cài đặt, ta sẽ không thực sự "xóa" đỉnh ra khỏi đồ thị mà ta chỉ cần dùng mảng để đánh dấu là đỉnh đó đã bị "xóa". Ta sẽ chứng minh:
Chứng minh: Ta sẽ chứng minh nếu $(u\rightarrow v) \in \vec{E}$ thì $u$ sẽ được gán chỉ số nhỏ hơn $v$. Giả sử ngược lại, tồn tại cung mà $u\rightarrow v$ được gán chỉ số lớn hơn $v$. Từ đó suy ra khi ta gán chỉ số cho $u$, $v$ đã được gán chỉ số rồi, và do đó, sẽ bị xóa khỏi đồ thị. Do đó, $v$ đã được đưa vào trong $S$ trước khi $u$ bị xóa khỏi $G$. Nhưng điều đó có nghĩa là khi $v$ vào $S$, cung $(u\rightarrow v)$ vẫn thuộc $G$, trái với điều kiện khi ta đưa $v$ vào $S$. Do đó, cung như vậy không tồn tại. Hay nói cách khác, đầu ra của thuật toán là một sắp xếp Topo.
Phân tích thuật toán: Ta sẽ dùng danh sách kề, với mỗi đỉnh $u$, danh sách kề của $u$ chỉ lưu các đỉnh mà $(u\rightarrow v) \in \vec{E}$. Hay nói cách khác, danh sách kề của $u$ chỉ lưu các out-neighbor của $u$. Ta sẽ dùng một mảng $Del[1,2\ldots, n]$ để đánh dấu đỉnh nào đã bị "xóa" ra khỏi đồ thị, i.e $Del[u] =$ True nếu $u$ bị xóa và False nếu ngược lại.
Thao tác khó nhất là kiểm tra xem sau khi xóa $s$ khỏi đồ thị, $v$ có trở thành đỉnh nguồn hay không (dòng if có comment ở giả mã trên). Ta có thể thực thi bằng cách duyệt qua các hàng xóm tới $u$ (in-neighbors) của $v$ và kiểm tra xem $Del[u] = $ True hay không. Nếu mọi hàng xóm tới của $v$ đều đã bị xóa, $v$ sẽ là đỉnh nguồn và ta đưa $v$ vào $S$. Tuy nhiên, để làm như vậy, ta phải lưu thêm một danh sách các hàng xóm tới cho mỗi đỉnh, và nếu không cẩn thận, mỗi thao tác duyệt sẽ mất thời gian là bậc tới của $v$, do đó làm cho tổng thời gian thành $O(m^2)$.
Để giải quyết tình trạng này, ta sẽ lưu thêm một mảng $Din[1,2\ldots,n]$ trong đó $Din[v] = d$ nếu bậc tới (in-degree) của $v$ là $d$ trong đồ thị hiện tại (không tính các đỉnh đã "xóa"). Do đó, mỗi lần "xóa" $s$ ra khỏi đồ thị, ta chỉ việc cập nhật lại mảng $Din[1,\ldots,n]$ và đỉnh điều kiện ở dòng if sẽ trở thành $Din[v] = 0$ (xem giả mã dưới đây). Do đó, thao tác kiểm tra này mất $O(1)$. Như vậy, tổng thời gian của thuật toán là $O(n+m)$.
Giả mã:
set all elements of $Del[1,\ldots, n]$ to False
$Din[1,\ldots, n] \leftarrow $ FindDin($G(V,\vec{E})$))
$S \leftarrow$ all source vertices of $G(V,\vec{E})$
$i \leftarrow 1$
while $S \not= \emptyset$
$s \leftarrow $ a vertex from $S$
$Ts[s] \leftarrow i$
$i \leftarrow i+1$
$Del[s] \leftarrow$ True
for each out-neighbor $v$ of $s$ in $G(V,\vec{E})$ [[$(s\rightarrow v) \in \vec{E}$]]
$Din[v] \leftarrow Din[v]-1$
if $Din[v] = 0$ [[$v$ become a sink]]
put $v$ to $S$
output $Ts[1,2,\ldots,n]$
set all elements of $Din[1,\ldots, n]$ to 0
for each arc $(u\rightarrow v) \in \vec{E}$
$Din[v] \leftarrow Din[v]+ 1$
return $Din[1,2,\ldots,n]$
Code C:
#define UNVISITED 0 #define VISITING 1 #define VISITED 2 #define TRUE 1 #define FALSE 0 // the vertex list data structure, it is a linked list typedef struct vlist{ int v; // vertex v is adjacent to the index of the list struct vlist *next; }vlist; vlist **G; // G[u] is the adjacency list of G int n; // the number of veritces int m; // the number of edges int *topo_sort(){ int *Del = (int *)malloc(n*sizeof(int)); memset(Del, FALSE, n*sizeof(int)); int *Din = find_din(); // find in-degree of all vertices int *Ts = (int *)malloc(n*sizeof(int)); // the topological order memset(Ts, 0, n*sizeof(int)); mark = (int *)malloc(n*sizeof(int)); memset(mark, UNVISITED, n*sizeof(int)); vlist *S = find_sources(); int i = 1; int s; while(S != NULL){ s = S->v; S = S->next; // remove s from S Ts[s] = i; i++; Del[s] = TRUE; // loop through all neighbors of s; vlist *runner = G[s]; int v; while(runner != NULL){ v = runner->v; Din[v] --; if(Din[v] == 0){ // add v to S vlist *node = malloc(sizeof(vlist)); node->v = v; node->next = S; S = node; } runner = runner->next; } } return Ts; } int *find_din(){ int *Din = (int *)malloc(n*sizeof(int)); memset(Din, 0, n*sizeof(int)); // loop through all edges of G to find in-degree of vertices int u = 0; vlist *nbrRunner; for(; u < n; u++){ nbrRunner = G[u]; while(nbrRunner != NULL){ Din[nbrRunner->v] ++; nbrRunner = nbrRunner->next; } } return Din; } // we use vlist as a linked list of sources vlist *find_sources(){ int *M = (int *)malloc(n*sizeof(int)); // array M to mark which vertex is not a source memset(M,0,n*sizeof(int)); // loop through all edges of G to find sources int u = 0; vlist *nbrRunner; for(; u < n; u++){ nbrRunner = G[u]; // the list of out-neighbors of u while(nbrRunner != NULL){ M[nbrRunner->v] = 1; // v is not a source nbrRunner = nbrRunner->next; } } vlist *head = NULL; // the head of the source list for( u = 0; u < n; u++){ if(M[u] == 0){ // u is a source vlist *node = malloc(sizeof(vlist)); node->v = u; node->next = head; head = node; } } return head; }
Remark: Theo Wikipedia, giải thuật sắp xếp Topo mà ta mô tả ở đây được phát triển bởi Kahn [1] năm 1966. Ngoài ra còn giải thuật khác sử dụng DFS khá giống với thủ tục DAGChcker. Giải thuật này được mô tả bởi Tarjan [2] vào năm 1974 và được sử dụng trong textbook CLRS[3].
Code đầy đủ: arc-classification, dag-checker, topo-sort.
Tham khảo
[1] Kahn, Arthur B. Topological sorting of large networks. Communications of the ACM 5.11 (1962): 558-562.
[2] Tarjan, Robert Endre. Edge-disjoint spanning trees, dominators, and depth-first search. Computer Science Department, School of Humanities and Sciences, Stanford University, 1974.
[3] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). Chapter 22.5. MIT Press and McGraw-Hill.
Recent Comments