Trong bài này và loạt bài tiếp theo chúng ta sẽ làm quen với đồ thị và các thuật toán với đồ thị. Đồ thị là một đối tượng tổ hợp (combinatorial object) được nghiên cứu và ứng dụng rất nhiều trong thực tế (có lẽ hơi thừa khi viết điều này). Phần này chúng ta sẽ:
- Làm quen với các khái niệm cơ bản gắn với đồ thị
- Cách biểu diễn đồ thị trong máy tính để chúng ta có thể thao tác với nó
- Duyệt đồ thị theo chiều rộng (Breadth First Search)
- Duyệt đồ thị theo chiều sâu (Depth First Search)
Bạn đọc có thể bỏ qua các phần mà các bạn đã quen thuộc. Note [1] của Jeff Erickson vẫn là tài liệu tham khảo chính của bài này.
Các khái niệm
Một đồ thị, kí hiệu là $G(V,E)$, gồm hai thành phần:
- Tập hợp $V$, bao gồm các đối tượng, được gọi là tập hợp các đỉnh (vertex) của đồ thị
- Tập hợp $E \subseteq V^2$, bao gồm một cặp các đỉnh, được gọi là tập hợp các cạnh (vertex) của đồ thị
Ta sẽ kí hiệu $n,m$ lần lượt là số đỉnh và số cạnh của đồ thị, i.e, $|V| = n, |E|= m$. Số đỉnh của đồ thị đôi khi ta cũng gọi là bậc của đồ thị (order of the graph).
Các đỉnh ta sẽ kí hiệu bằng các chữ in thường như $u,v,x,y,z$. Cạnh giữa hai đỉnh $u,v$ có thể là vô hướng hoặc có hướng. Trong trường hợp đầu ta sẽ kí hiệu cạnh là $uv$, còn trong trường hợp sau ta sẽ kí hiệu là $u \rightarrow v$ để chỉ rõ hướng của cạnh là từ $u$ đến $v$. Thông thường khi ta nói cạnh thì ta ám chỉ cạnh vô hướng còn với một cạnh có hướng ta sẽ gọi nó là một cung (arc). Hình $(1,2)$ của hình dưới đây biểu diễn một đồ thị vô hướng (các cạnh là vô hướng) và hình $(3)$ phải của hình dưới đây biểu diễn một đồ thị có hướng.
Trong hình $(1)$, cạnh $(a,a)$ được gọi là cạnh lặp (loop) và hai cạnh giữa cặp đỉnh $(b,d)$ được gọi là hai cạnh song song (parallel edges). Một đồ thị được gọi là một đơn đồ thị (simple graph) nếu nó không có cạnh lặp và cạnh song song (hình $(2)$). Nếu một đồ thị không phải là đơn đồ thị thì chúng ta sẽ goị nó là đa đồ thị (multigraph). Trong các loạt bài đồ thị ở đây, ta chủ yếu xét đơn đồ thị. Do đó, khi nói đồ thị ta sẽ ngầm hiểu là đơn đồ thị. Ta có:
Nếu đồ thị $G(V,E)$ vô hướng, với mỗi cạnh $uv$, đỉnh $v$ được gọi là kề (incident) với cạnh $uv$. Đỉnh $u$ được gọi là hàng xóm (neighbor) của $v$. Bậc (degree) của đỉnh $v$, thường kí hiệu là $d(v)$, là số hàng xóm của đỉnh $v$. Nếu đồ thị $G(V,E)$ có hướng, với mỗi cung $u\rightarrow v$, đỉnh $v$ được gọi là đỉnh liền sau (successor) của $u$ và đỉnh $u$ được gọi là đỉnh liền trước (predecessor) của $v$. Bậc tới (in-degree) của $v$ là số đỉnh liền trước $v$ và bậc lui (out-degree) của $v$ là số đỉnh liền sau $v$. Ví dụ bậc tới của $d$ trong hình $(3)$ là 1 và bậc lui là $3$.
Ta gọi $H(V_H, E_H)$ là đồ thị con (subgraph) của $G$ nếu $V_H \subseteq V$ và $E_H \subseteq E$.
Một đường đi (walk) là một dãy các cạnh $\{e_1,e_2,\ldots, e_k\}$ trong đó hai cạnh liền kề bất kì $e_i$ và $e_{i+1}$ đều có chung một đỉnh.
Chú ý là đường đi có thể đi qua một đỉnh nhiều lần. Trong trường hợp mỗi đỉnh được thăm đúng 1 lần, ta sẽ gọi đó là đường đi đơn (path). Ví dụ trong đồ thì ở hình dưới đây, $\{ab,bc,ca,ae,ed,dc\}$ là một đường đi giữa $a$ và $c$ và $\{ab,bd,dc\}$ là một đường đi đơn giữa $a$ và $c$. Một đường đi đóng (closed walk) là một đường đi bắt đầu và kết thục tại cùng một điểm. Một chu trình (cycle) là một đường đi đơn bắt đầu và kết thúc tại cùng một điểm. Có thể nói một chu trình là một đường đi đóng đi qua mỗi điểm đúng 1 lần ngoại trừ điểm đầu và điểm cuối. Các khái niệm vừa rồi nếu áp dụng cho đồ thị có hướng thì ta sẽ thêm từ "có hướng" vào đằng trước.
Một đồ thị vô hướng được gọi là liên thông (connected) nếu tồn tại một đường đi giữa mọi cặp điểm. Một đồ thị có hướng gọi là liên thông (yếu) nếu đồ thị vô hướng thu được từ đồ thị đó bằng cách bỏ qua hướng của cạnh là liên thông. Một đồ thị có hướng gọi là liên thông mạnh (strongly connected) nếu tồn tại một đường đi có hướng giữa mọi cặp điểm. Hiển nhiên nếu một đồ thị có hướng liên thông mạnh thì nó cũng liên thông yếu. Tuy nhiên điều ngược lại chưa chắc đúng (ví dụ?). Ví dụ đồ thị $(1)$ dưới đây là không liên thông, đồ thị $(2)$ liên thông, đồ thị $(3)$ liên thông yếu (nhưng không mạnh) và đồ thị $(4)$ liên thông mạnh.
Nếu một đồ thị (vô hướng) không liên thông, tập các đỉnh liên thông với nhau tạo thành một thành phần liên thông (connected component). Tương tự như vậy ta có thể định nghĩa thành phần liên thông (yếu hay mạnh) cho đồ thị có hướng. Một đồ thị không có chu trình (acyclic) thì ta gọ là một rừng (forest). Một rừng chỉ có một thành phần liên thông thì ta gọi nó là một cây (tree). Khái niệm cây và rừng có hướng tương tự như đồ thị có hướng.
Có lẽ ta sẽ dừng định nghĩa khái niệm ở đây. Còn rất rất nhiều các khái niệm khác chúng ta sẽ định nghĩa khi mà chúng ta cần. Gần như tất cả các khái niệm cơ bản đã được liệt kê ở [2] mà bạn đọc có thể tham khảo thêm.
Trong phần tiếp theo, ta xét $G(V,E)$ vô hướng. Các thao tác với đồ thị có hướng có thể được mở rộng và áp dụng một cách tương tự.
Biểu diễn đồ thị
Chúng ta có thể biểu diễn đồ thị bằng một ma trận kề (adjacency matrix) $A$ có kích thước $n \times n$ trong đó:
$A[u,v] = \begin{cases} 1, & \mbox{if } uv \in E\\ 0, & \mbox{otherwise } \end{cases} \qquad (1)$
Có thể thấy ngay là kích thước của cách biểu diễn này là $O(n^2)$ bất kể số lượng cạnh là nhiều hay ít. Theo Fact 1, số lượng cạnh $m$ của một đồ thị có thể lên tới $O(n^2)$ cạnh (ta gọi là đồ thị dầy). Do đó, cách biểu diễn này có thể nói là phù hợp với đồ thị dầy. Tuy nhiên, nhiều đồ thị (đặc biệt các đồ thị thực tế như mạng xã hôi), số lượng cạnh $m = O(n)$ (ta gọi là đồ thị thưa). Do đó cách biểu diễn này khá tốn kém với đồ thị thưa.
Để tiết kiệm bộ nhớ, với mỗi đỉnh $u \in V$, ta lưu trữ một danh sách các đỉnh kề với nó. Như vậy, đỉnh $u$ cần một danh sách có $d(u)$ phần tử. Do đó tổng số phần tử của các danh sách là:
$\sum_{u \in V}d(v) = 2m \qquad (2)$
Tổng $\sum_{u \in V}d(v) = 2m$ là do mỗi cạnh được đếm hai lần trong tổng bậc của hai đỉnh kề với nó. Cách biểu diễn như trên gọi là biểu diễn bằng danh sách kề (adjacency list). Cách biểu diễn này phù hợp với cả đồ thị thưa. Mặc dù tiết kiệm bộ nhớ, cách biểu diễn này không phù hợp với một số thao tác của đồ thị. Bảng dưới đây so sánh hai cách biểu diễn vừa trình bày.
Adjacency matrix | Adjacency list (linked list) | |
Space | $O(n^2)$ | $O(n+m)$ |
Test $uv \in E$ | $O(1)$ | $O(1 + \min(d(u),d(v)))$ |
List all neighbors of $v$ | $O(n)$ | $O(1+d(v))$ |
Add an edge $uv$ | $O(1)$ | $O(1)$ |
Delete an edge $uv$ | $O(1)$ | $O(d(u)+d(v)) = O(n)$ |
Ví dụ về hai cách biểu diễn đồ thị cho trong hình dưới đây:
Ta còn có thể kết hợp cách biểu diễn danh sách kề với một vài cấu trúc dữ liệu khác. Cụ thể, thay vì dùng danh sách liên kết để biểu diễn các đỉnh kề với một đỉnh $u$, ta còn có thể dùng bảng băm hoặc cấu trúc cây để biểu diễn. Trong khuôn khổ các bài viết ở đây, ta ít dùng (hoặc không dùng) các cấu trúc như vậy.
Ngoài ra ta có thể biểu diễn đồ thị bằng cách liệt kê tất cả các cặp $(u,v)$ thỏa mãn $uv \in E$. Cách biểu diễn này có bộ nhớ là $O(m)$. Tuy nhiên, việc thực hiện các thao tác cơ bản trong cách biểu diễn này sẽ rất tốn kém. Đôi khi, ta có thể kết hợp cách biểu diễn này với cách biểu diễn danh sách kề để tận dụng ưu thế của cả hai cách biểu diễn mà bộ nhớ vẫn là tuyến tính.
Duyệt đồ thị
Ta gọi bài toán trên là bài toán duyệt đồ thị từ một đỉnh $s$. Để đơn giản, ta sẽ giả sử đồ thị là liên thông. Trường hợp đồ thị không liên thông sẽ được mở rộng ở cuối phần này. Cách thức chung để duyệt đồ thị như sau: Ta sẽ sử dụng 2 loại nhãn để gán cho các đỉnh của đồ thị: chưa thăm (unvisited) và đã thăm (visited). Ban đầu tất cả các đỉnh được đánh dấu là chưa thăm (unvisited). Ta sẽ duy trì một tập hợp $C$ (thực thi tập $C$ thế nào ta sẽ tìm hiểu sau), ban đầu khởi tạo rỗng. Ta sẽ thực hiện lặp 2 bước sau:
- Lấy ra một đỉnh $u$ trong $C$ (thủ tục Remove$(C)$ dưới đây).
- Đánh dấu $u$ là đã thăm (visited).
- Đưa các hàng xóm của $u$ có nhãn chưa thăm vào trong $C$. Thủ tục Add$(C,v)$ dưới đây sẽ đưa đỉnh $v$ vào trong tập $C$.
Thuật toán dừng khi $C = \emptyset$. Giả mã như sau:
mark all vertices unvisited
Add$(C,s)$
while $C \not= \emptyset$
$u \leftarrow$ Remove$(C)$ $\ll(*)\gg$
if $u$ is unvisited
mark $u$ visited
for all $uv \in E$ and $v$ is unvisited $\ll(**)\gg$
Add$(C,v)$
Remark: Một đỉnh có thể được đưa nhiều lần vào tập $C$ (do đó $C$ không hẳn là tập hợp vì có nhiều phần tử giống nhau). Ví dụ xét 3 đỉnh $u,v,w$ đôi một kề nhau. Đỉnh $u$ được lấy ra từ $C$ đầu tiên; đánh dấu $u$ là đã thăm. Ngay sau đó, $v$ và $w$ sẽ được đưa vào $C$. Tiếp theo, lấy $v$ ra khỏi $C$ và đánh dấu $v$ là đã thăm. Lúc này ta lại tiếp tục đưa $w$ vào $C$ một lần nữa vì theo giả mã trên, $w$ là hàng xóm của $v$ và có nhãn chưa thăm. Ở đây, ta sẽ không kiểm tra xem một đỉnh đã nằm trong $C$ hay chưa trước khi đưa vào $C$.
Từ giả mã trên, ta thấy, tập $C$ lưu các đỉnh kề với ít nhất một đỉnh đã thăm.
Phân tích thuật toán: Giả sử rằng ta sử dụng một cấu trúc để thực thi $C$ sao cho việc thêm vào hoặc lấy một đỉnh bất kì (dòng $(*)$ và dòng cuối cùng) được thực hiện trong thời gian $O(1)$ (ví dụ nếu thưc thi $C$ bằng danh sách liên kết thì thêm vào hoặc lấy ra đỉnh ở đầu danh sách có thể được thực hiện trong thời gian $O(1)$). Ta có một vài nhận xét sau:
- Các đỉnh đã được lấy ra khỏi $C$ và bị đánh dấu là đã thăm thì nó sẽ không bao giờ được đưa trở lại tập $C$ nữa.
- Mỗi lần đỉnh $v$ được đưa vào $C$, một hàng xóm của nó sẽ bị đánh dấu là đã thăm. Do đó, đỉnh $v$ sẽ bị đưa vào $C$ không quá $d(v)$ lần.
- Mỗi khi lấy một đỉnh $u$ ra khỏi $C$, ta sẽ duyệt qua tất cả các hàng xóm của $u$. Thao tác này mất thời gian $O(d(u))$. Theo nhận xét 1, phép duyệt này chỉ được thực hiện tối đa 1 lần.
Từ các nhận xét trên, ta suy ra tổng thời gian tính toán của thuật toán là $O(\sum_{u \in V}d(u)) = O(m)$.
Trong trường hợp đồ thị không liên thông, ta phải duyệt qua từng thành phần liên thông một. Do đồ thị có tối đa $n$ thành phần liên thông, ta có:
Nếu ta thực thi $C$ bằng danh sách liên kết thì có lẽ không có gì thú vị cả. Tuy nhiên, nếu ta thực thi $C$ bằng hàng đợi (Queue) hoặc ngăn xếp (Stack) thì ta sẽ thu được một số tính chất thú vị từ đồ thị. Trường hợp ta thực thi $C$ bằng hàng đợi, ta gọi thuật toán là duyệt theo chiều rộng (Breath First Search - BFS). Trường hợp ta thực thi $C$ bằng ngăn xếp, ta gọi thuật toán là duyệt theo chiều sâu (Depth First Search - DFS). Sau đây ta sẽ thảo luận cả hai thuật toán.
Thuật toán duyệt theo chiều rộng BFS
Như đã nói ở trên, thuật toán BFS sẽ thực thi $C$ bằng hàng đợi. Ta sẽ thay thủ tục Add$(C,v)$ bằng thủ tục Enqueue$(C,v)$ và thủ tục Remove$(C)$ bằng thủ tục Dequeue$(C)$. Ngoài khung cơ bản như thuật toán ở trên, ta sẽ gán cho mỗi đỉnh $v$ một nhãn $d[v]$. Giá trị của $d[v]$, như ta sẽ chỉ ra dưới đây, là khoảng cách ngắn nhất từ $s$ tới $v$. Giả mã như sau:
for each $v \in V$
$d[v] \leftarrow +\infty$
$C\leftarrow$ an empty Queue
Enqueue$(C,s)$
$d[s] \leftarrow 0$
while $C \not= \emptyset$
$u \leftarrow$ Dequeue$(C)$
if $u$ is unvisited
mark $u$ visited
for all $uv \in E$ and $v$ is unvisited $\ll(**)\gg$
Enqueue$(C,v)$
$d[v] \leftarrow d[u]+1$
Code của giả mã bằng C:
#define UNVISITED 0 #define VISITED 1 #define TRUE 1 #define FALSE 0 #define INFTY 1000000 // 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 *D; // the distance of vertices from BFS int* mark; // an array to mark visited vertices typedef struct Queue{ int *storage; int back, front; }Queue; void bfs(int s){ printf("executing bfs.....\n"); D = (int *)(malloc(n*sizeof(int))); int i = 0; for(; i < n; i++) D[i] = INFTY; Queue *Q = init_queue(n); enqueue(Q,s); D[s] = 0; int u; int v; while(!is_queue_empty(Q)){ u = dequeue(Q); if(mark[u] == UNVISITED){ printf("visiting %d\n",u); mark[u] = VISITED; // loop through adjaceny list of u vlist *runner = G[u]; while(runner != NULL){ v = runner->v; if(mark[v] == UNVISITED){ D[v] = D[u]+1; enqueue(Q,v); } runner = runner->next; } } } printf("done bfs\n"); } //////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////// //////////////// THE QUEUE INTERFACES //////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////////// Queue *init_queue(int size){ Queue *Q = malloc(sizeof(Queue)); Q->storage = (int *)malloc(size*sizeof(int)); Q->front = 0; Q->back = -1; return Q; } void enqueue(Queue *Q, int elem){ Q->back ++; Q->storage[Q->back] = elem; } int dequeue(Queue *Q){ if(is_queue_empty(Q)) { printf("nothing to dequeue\n"); exit(0); } int elem = Q->storage[Q->front]; Q->front++; return elem; } int is_queue_empty(Queue* Q){ return Q->back < Q->front? TRUE : FALSE; }
Ví dụ ta thực thi thuật toán trên với đồ thị trong hình bên trái và kết qủa thu được trong hình bên phải. Các số ứng với các đỉnh tương ứng là nhãn của các đỉnh đó. Những cạnh màu đỏ laf những cạnh mà $v$ có nhãn unvisited ở dòng $(**)$ được thăm bởi BFS.
Chứng minh: Gọi mức (level) của một đỉnh $u$, kí hiệu là $level(u)$, là khoảng cách ngắn nhất từ đỉnh $s$ tới $u$. Trong ví dụ trên, đỉnh $b,c,e$ có mức $1$, $d,h$ có mức 2, .... Bằng quy nạp, ta có thể chứng minh rằng (coi như bài tập cho bạn đọc):
Claim: Các đỉnh ở mức $i$ sẽ được thăm sau các đỉnh ở các mức $1,2,\ldots, i-1$.
Ta quy nạp trên biến $level$ để chứng minh rằng nhãn của $v$ cũng chính là mức của $v$, i.e, $level(v) = d[v]$.
Xét một đỉnh $v$. Lần đầu tiên $v$ được đưa vào hàng đợi $C$ là khi ta thăm một đỉnh $u$ nào đó kề với $v$ và theo Claim trên, mức của $u$ sẽ nhỏ hơn mức của $v$. Từ định nghĩa của mức ta suy ra $level(u) = level(v)-1$. Theo giả thiết quy nạp $d[u] = level(u)$, ta suy ra $level(v) = d[u] +1$. Theo giả mã, khi đưa $v$ vào hàng đợi, ta cập nhật $d[v] = d[u+1]$. Do đó, $d[v] = lelve(v)$, dpcm.
Kết hợp Theorm 1 và Theorem 2 ta có hệ quả sau:
Corollary 1 có ý nghĩa rất lớn vì ta sẽ thấy (trong bài thuật toán Dijkstra), thuật toán tốt nhất tìm đường đi ngắn nhất với đồ thị có trong số có thời gian $O(n\log n)$ ngay cả trong đồ thị thưa (m = O(n)). Thuật toán BFS sẽ là thuật toán đơn giản và hiệu quả để tìm đường đi ngắn nhất trong đồ thị không có trong số.
Thuật toán duyệt theo chiều sâu DFS
Trong duyệt theo chiều sâu DFS, ta thực thi $C$ sử dụng ngăn xếp. Ta sẽ thay thủ tục Add$(C,v)$ bằng thủ tục Push$(C,v)$ và thủ tục Remove$(C)$ bằng thủ tục Pop$(C)$.
$C\leftarrow$ an empty Stack
Push$(C,s)$
while $C \not= \emptyset$
$u \leftarrow$ Pop$(C)$
if $u$ is unvisited
mark $u$ visited
for all $uv \in E$ and $v$ is unvisited $\ll(**)\gg$
Push$(C,v)$
Code của giả mã bằng C:
#define UNVISITED 0 #define VISITED 1 #define TRUE 1 #define FALSE 0 #define INFTY 1000000 // 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 *D; // the distance of vertices from BFS int* mark; // an array to mark visited vertices typedef struct Stack { int *storage; int top; } Stack; void dfs(int s){ printf("executing dfs.......\n"); Stack *S = init_stack(n); push(S, s); int u; int v; while(!is_stack_empty(S)){ u = pop(S); if(mark[u] == UNVISITED){ printf("visiting %d\n",u); mark[u] = VISITED; // loop through neighbors of u vlist *runner = G[u]; // the ajdacency list of u while(runner!= NULL){ v = runner->v; if(mark[v] == UNVISITED){ push(S,v); } runner = runner->next; } } } printf("done dfs\n"); } //////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////// //////////////// THE STACK INTERFACES //////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////////// Stack *init_stack(int size){ Stack *S = (Stack *)malloc(sizeof(Stack)); S->top = -1; S->storage = (int*)malloc(size*sizeof(int)); return S; } void push(Stack *S, int elem){ S->top++; S->storage[S->top] = elem; } int pop(Stack *S){ if(is_stack_empty(S)){ printf("nothing to pop\n"); exit(0); } int elem = S->storage[S->top]; S->top--; return elem; } int is_stack_empty(Stack *S){ return S->top < 0 ? TRUE: FALSE; }
Nếu chỉ nhìn qua thi không thấy sự khác biệt qúa nhiều giữa DFS và thuật toán chung để duyệt đồ thị. Tuy nhiên bằng cách cập nhật thêm một vài thông tin trong quá trình duyệt đồ thị (giống như BFS), ta có thể phát hiện ra những tính chất rất thú vị của DFS. Ta sẽ thảo luận những tính chất đó ở bài sau. Hình dưới đây là một ví dụ thực thi DFS trên đồ thị. Số tương ứng của mỗi đỉnh ở bên phải là thứ tự của đỉnh thăm bởi DFS.
Ngoài thủ tục lặp DFS sử dụng ngăn xếp như trên, có lẽ một trong số chúng ta cũng khá quen thuộc với thủ tục thực thi DFS sử dụng đệ quy sau:
Code của giả mã bằng
void recursive_dfs(int s){ printf("visiting %d\n",s); mark[s] = VISITED; // loop through neighbors of s int v = 0; for(; v < n; v++){ if(G[s][v] == 1 && mark[v] == UNVISITED){ recursive_dfs(v); } } }
Ta thấy cách thứ hai đơn giản hơn do không phải thực thi Stack. Tuy nhiên, cách này sẽ sử dụng nhiều Call Stack của máy tính và trong trường hợp độ sâu đệ quy lớn có thể gây ra Stack Overflow.
Phát hiện các thành phần liên thông
Một trong những ứng dụng đơn giản nhất để duyệt đồ thị là phát hiện ra các thành phần liên thông. Để phát hiện ra các thành phần liên thông của đồ thị (vô hướng), ta thực hiện lặp lại thao tác sau: chọn một đỉnh chưa thăm $u$ và thực hiện thăm các đỉnh trong thành phần liên thông chứa $u$. Thủ tục sau đây trả lại số thành phần liên thông của đồ thị đầu vào $G(V,E)$.
mark all vertices unvisited
$count \leftarrow 0$
for all vertices $s\in V$
if $s$ is unvisited
GraphTraversal($G(V,E),s$) [[any graph traversal algorithm]]
$count\leftarrow count+1$
return $count$
Code C:
int connected_component(){ memset(mark, UNVISITED, (n+1)*sizeof(int)); // mark all vertices unvisited int s = 0; int count = 0; for(; s < n; s++){ if(mark[s] == UNVISITED){ bfs(s); count++; } } return count; }
Code đầy đủ: list-representation, matrix-representation.
Tham khảo
[1] Jeff Erickson, Graph Lecture Note, UIUC.
[2] Diestel, Reinhard. Graph theory. 2005. Grad. Texts in Math (2005).
[3] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (2nd ed.), Chapter 23. MIT Press and McGraw-Hill (2001). ISBN 0-262-03293-7.
Tags: bfs, connected component, dfs, graph basic, graph intro, graph representation
No comments
Comments feed for this article
Trackback link: http://www.giaithuatlaptrinh.com/wp-trackback.php?p=553