dfs

You are currently browsing articles tagged dfs.

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:

DFSAllA($G(V,\vec{E})$):
    mark all vertices unvisited
    for each vertex $v$
        if $u$ is unvisited
            RecursiveDFS($u$)         [[$(*)$]]

 

RecursiveDFSA($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):

PrintReversePath($v, P[1,2,\ldots,n]$):
    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:

DFSAllB($G(V,\vec{E})$):
    mark all vertices unvisited
    for each vertex $v$
        if $u$ is unvisited
            $P[u] \leftarrow \emptyset$
            $L[u] \leftarrow u$
            RecursiveDFS($u$)         [[$(*)$]]

 

RecursiveDFSB($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.

dfs-forest

Gọi $\vec{E_{dfs}}$ là tập các cung được thăm bởi DFS. Ta có:

Lemma 1: Đồ thị $G_{dfs}(V, \vec{E_{dfs}})$ là một rừng gồm $k$ cây có hướng $\vec{T_1},\ldots, \vec{T_k}$ trong đó mỗi cây $T_i$ có gốc tại $u_i$ biểu diễn tập các đỉnh đến được từ $u_i$.

 
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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

arc-classification

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:

  1. 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.
  2. 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.
  3. 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à:

  1. Đỉnh $v$ là unvisited thì $u \rightarrow v$ là cung của cây DFS.
  2. Đỉ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.
  3. Đỉ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:

DFSAllC($G(V,\vec{E})$):
    mark all vertices unvisited
    for each vertex $v$
        if $u$ is unvisited
            RecursiveDFS($u$)         [[$(*)$]]

 

RecursiveDFSC($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:

Problem 1: Cho đồ thị có hướng $G(V,\vec{E})$, kiểm tra xem $G(V,\vec{E})$ có phải là một DAG hay không.

 

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:

Fact 1: Nếu $G(V,\vec{E})$ là một DAG thì $G(V, \overleftarrow{E})$ cũng là một DAG.

 

Đỉ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.

source-sink-ex

Ta có bổ đề sau:

Lemma 2: Nếu $G(V,\vec{E})$ là một DAG thì nó có ít nhất một đỉnh phát và một đỉnh thu.

 
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:

Lemma 3: Đồ thị $G_s(V_s,\vec{E}_s)$ là DAG khi và chỉ khi cây DFS gốc tại $s$ không có cung ngược.

 
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:

DAGChecker($G(V,\vec{E})$):
    $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.

 

DFSChecker($u$):
    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)$.

Theorem 1: Kiểm tra đồ thị có hướng $G(V,\vec{E})$ có phải là DAG hay không có thể được thực hiện trong thời gian $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).

topo-sort-ex

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ó:

Theorem 2: $G(V,\vec{E})$ có sắp xếp Topo khi và chỉ khi $G(V,\vec{E})$ là một DAG.

 

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:

TopoSort($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$
        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:

Lemma 4: Đầu ra của thuật toán TopoSort là một sắp xếp Topo nếu như đồ thị đầu vào là DAG.

 
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)$.

Theorem 2: Ta có thể tìm được một sắp xếp Topo cho đồ thị DAG $G(V,\vec{E})$ trong thời gian $O(n+m)$.

 

Giả mã:

PracticalTopoSort($G(V,\vec{E})$):
    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]$

 

FindDin($G(V,\vec{E})$):
    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-&gt;v;
S = S-&gt;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-&gt;v;
Din[v] --;
if(Din[v] == 0){
// add v to S
vlist *node = malloc(sizeof(vlist));
node-&gt;v = v;
node-&gt;next = S;
S = node;
}
runner = runner-&gt;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 &lt; n; u++){
nbrRunner = G[u];
while(nbrRunner != NULL){
Din[nbrRunner-&gt;v] ++;
nbrRunner = nbrRunner-&gt;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 &lt; n; u++){
nbrRunner = G[u];		// the list of out-neighbors of u
while(nbrRunner != NULL){
M[nbrRunner-&gt;v] = 1;	// v is not a source
nbrRunner = nbrRunner-&gt;next;
}
}

vlist *head = NULL;	// the head of the source list

for( u = 0; u &lt; n; u++){
if(M[u] == 0){	// u is a source
vlist *node  = malloc(sizeof(vlist));
node-&gt;v = u;
node-&gt;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.

Tags: , , , ,

« Older entries