03 - Các thuật toán duyệt trên đồ thị

Giới thiệu

Sau khi đã hiểu được cách lưu trữ được đồ thị trong máy tính, chúng ta bắt đầu khảo sát đến những ứng dụng của lý thuyết đồ thị trong thực tế. Rất nhiều ứng dụng ngày nay dựa trên mô hình đồ thị. Tuy nhiên, bước đầu tiên để đi vào những ứng dụng đó cũng như các giải thuật xử lý đi kèm, chúng ta cần thêm một bước quan trọng nữa, đó là làm sao duyệt qua được hết các cạnh hay các đỉnh của đồ thị.

Cho đến nay, hai hướng tiếp cận phổ biến nhất là duyệt theo chiều sâu (Deep Firt Search - DFS) và duyệt theo chiều rộng (Breadth First Search - BFS). Cả hai đều làm theo một nguyên tắt là bắt đầu từ một đỉnh v, duyệt qua các đỉnh kề với v mà chưa được thăm, đánh dấu lại đã thăm rồi cứ vậy tiếp tục đến khi đã thăm hết các đỉnh. Tuy nhiên, vì cách sử dụng cấu trúc dữ liệu khác nhau (Stack cho DFS và Queue cho BFS) khiến thứ tự duyệt qua các đỉnh này khác hẳn nhau, từ đó mỗi cách duyệt sẽ phù hợp cho một nhánh các bài toán khác nhau.

Tài liệu tham khảo

1. Competitive Programming 4, Steven Halim

2. Tài liệu giáo khoa chuyên Tin 1, Hồ Sỹ Đàm

3. GeeksforGeeks

4. Giải thuật lập trinh - giaithualaptrinh.com

5. Wikipeadia

Duyệt theo chiều sâu - DFS

Giải thuật duyệt theo chiều sâu thực hiện theo quy trình đúng như tên gọi của nó. Bắt đầu từ 1 đỉnh v,  DFS chọn một trong các hàng xóm (các đỉnh kề) của v mà chưa được thăm để đến thăm. Sau đó nó đánh dấu đỉnh này đã thăm rồi lại tiếp tục với các hàng xóm chưa thăm của đỉnh này. Quá trình tiếp tục đến khi gặp một đỉnh mà không thể thăm sâu hơn được nữa nó sẽ backtrack về đỉnh trước đó rồi chọn lại hàng xóm chứa thăm kế tiếp.

DFS có thể được cái đặt dễ dàng bằng mô hình đệ quy, trong đó lưu ý đến hai trạng thái của một đỉnh là duyệt đến và duyệt xong (chưa thăm - unvisited và đã thăm - visited).

Giải thuật tổng quát:

B1. Khởi tạo toàn bộ các đỉnh trong V là chưa thăm

B2. Bắt đầu từ một đỉnh s được chọn.

B3. Đánh dấu s là đã thăm

B4. Xét các hàng xóm của s, chọn hàng xóm nhỏ nhất v, đánh dấu v đã thăm

B5. Quay lại được bước 2 với v

Thuật toán kết thúc khi tất cả các đỉnh đều đã thăm.

Ví dụ:

Thứ tự duyệt DFS cho ta danh sách các đỉnh được thăm lần lược là: A -->B-->D-->F-->E-->C-->G

Mã giả

Hướng tiếp cận đệ quy

procedure DFS(G, v) is

    label v as discovered

    for all directed edges from v to w that are in G.adjacentEdges(v) do

        if vertex w is not labeled as discovered then

            recursively call DFS(G, w)

Hướng tiếp cận khử đệ quy

procedure DFS_iterative(G, v) is

    let S be a stack

    S.push(v)

    while S is not empty do

        v = S.pop()

        if v is not labeled as discovered then

            label v as discovered

            for all edges from v to w in G.adjacentEdges(v) do 

                S.push(w)

Nguồn mã giả: wikipedia

Trong hướng tiếp cận khử đệ quy này, chúng ta dùng một stack S. Ban đầu ta đẩy đỉnh v vào Stack --> lấy s ra khỏi stack, đánh đấu đã thăm. Tiếp theo xét các hàng xóm w của v mà chưa được thăm, đẩy hết các w vào S rồi thực hiện lại việc xét từng w giống như v. Giải thuật kết thúc khi stack S đã rỗng.

Để hiểu rõ hơn quá trình hoạt động của DFS dựa trên Stack, các em quan sát từng bước thực hiện được trình bày trong GeeksforGeeks

Cài đặt:

Việc cài đặt theo hướng tiếp cận đệ quy có thể thực hiện như sau: chúng ta dùng một vector toàn cục vi dfs_num để lưu trạng thái thăm hay chưa thăm của các đỉnh. Ban đầu toàn bộ phần tử của vector này được đánh dấu là chưa thăm.

enum {UNVISITED = -1, VISITED = -2};           //basic flags

vi dfs_num;                 // sẽ khởi tạo toàn bộ vector này là chưa thăm trong main()

void dfs(int u){             

dfs_num[u] = VISITED;                  //Đánh dấu u đã thăm

for(auto &[v, w] : AL[u] )             //Xét các hàng xóm v của u

if(dfs_num[v] == UNVISITED)    //Nếu v chưa được thăm

dfs(v);                //đệ quy quá trình với v

}

Nguồn: CP4, Steven Halim

Cần lưu ý rằng thủ tục DFS ở trên chỉ duyệt được hết các đỉnh mà có đường đi từ u, nếu đồ thị không liên thông, các đỉnh của nó có thể không được duyệt hết. Chẳng hạn như đồ thị sau đây:

Rõ ràng thứ tự duyệt DFS(0) ở đây sẽ là 0 -->1-->2-->3-->4, các đỉnh 5, 6, 7, 8 sẽ không được duyệt đến.

Độ phức tạp

Độ phức tạp của DFS phụ thuộc rất nhiều vào cách ta lưu đỉnh, cạnh của nó. Giả định với đồ thị G(V, E) có n =|V| đỉnh và m = |E| cạnh. 

• Nếu ta lưu bằng ma trận kề, việc kiểm tra các hàng xóm mất chi phí O(n), và phải kiểm qua n đỉnh nên chi phí là O(n^2). 

• Nếu lưu bằng danh sách cạnh, với mỗi đỉnh v, muốn tìm hết hàng xóm của nó phải đi qua m cạnh --> O(n*m)

• Nếu lưu bằng danh sách kề, ta có thể truy xuất nhanh dựa trên mảng head[] (nếu lưu bằng mảng) hoặc thực hiện ngắt và truy cập đầu danh sách nếu lưu bằng danh sách liên kết, chi phí này là O(1). Như vậy thời gian duyệt qua bằng số cạnh của đồ thị --> O(m). Nếu đồ thị không liên thông, có nghĩa là nó có thể có tối đa n thành phần liên thông, thì DFS tổng thể tốn O(m + n)

==> như vậy, ta thấy rõ lợi thế của cách lưu bằng danh sách kề. Tuy nhiên, input của các bài toán thường là danh sách cạnh, nên chúng ta nên cần nhắc việc chuyển từ danh sách cạnh sang danh sách kề trước khi tiến hành DFS.

Để hiểu rõ hơn về lý do DFS trên đồ thị được lưu bằng danh sách kề chỉ tốn O(m) đối với đồ thị liên thông, các em quan sát lại đồ thị dưới đây:

Bắt đầu từ a, ta đánh dấu đã duyệt --> hàng xóm đầu tiên của nó là b, đánh dầu b đã duyệt, trong danh sách hàng xóm của b, vì a đã duyệt nên bị loại ra, con trỏ của b next thẳnng tới c (trong O(1)). Hàng xóm của c là a, b đều đã được đánh dấu đã thăm, next thẳng tới d. Hàng xóm của d là b, c đã duyệt --> next thẳng tới e. Hàng xóm của e là d và a đều đã được đánh dấu duyệt xong. Kết thúc.

Nhiệm vụ 1. Thực hiện bài toán tìm đường. Cho một đồ thị G(V, E), xuất phát từ một đỉnh s, hãy liệt kế các đỉnh tới được từ s. Cho một đỉnh t, hãy xuất ra một đường đi từ s tới t.

Ví dụ:

Nhiệm vụ 2. Duyệt theo chiều sâu - UPCODER

Duyệt theo chiều rộng - BFS

Duyệt theo chiều rộng là giải thuật duyệt theo thứ tự từng lớp. Bắt đầu từ đỉnh s, BFS duyệt qua các đỉnh kề trực tiếp với s, đây là lớp đầu tiên. Tiếp theo, với mỗi đỉnh u của lớp 1, giải thuật tiếp tục duyệt các hàng xóm v trực tiếp với nó, gọi là lớp 2, ...tiếp tục cho đến khi không còn lớp nào nữa, hay tất cả các đỉnh đã được duyệt qua.

Giải thuật tổng quát

B1. Bắt đầu từ đỉnh s, đẩy nó vào đuôi hàng đợi

B2. Lấy một đỉnh từ đầu hàng đợi đưa vào danh sách đã duyệt

B3. Tạo một danh sách các đỉnh kề với đỉnh vừa lấy ra, đẩy từng đỉnh này (chưa được duyêt) vào đuôi hàng đợi.

B4. Lặp lại bước 2 và bước 3 cho đến khi hàng đợi rỗng.

Ví dụ:

Thứ tự duyệt BFS cho đồ thị trên là: A -->B-->C-->E-->D-->F-->G

Mã giả

Cài đặt:

Thủ tục BFS sau đây được hỗ trợ bởi một hàng đợi q.

Để hiểu rõ hơn về cách hoạt động của BFS, các em có thể tham khảo các bước minh họa chi tiết trong GeeksforGeeks

Ứng dụng

BFS được sử dụng trong nhiều bài toán khác nhau như:

1. To build index by search index

2. For GPS navigation

3. Path finding algorithms

4. In Ford-Fulkerson algorithm to find maximum flow in a network

5. Cycle detection in an undirected graph

6. In minimum spanning tree

Độ phức tạp

Cũng giống như DFS, độ phức tạp của BFS cũng phụ thuộc vào cách lưu trữ đồ thị trong máy tính. Với đồ thị G = (V, E), n = |V| và m = |E|, độ phức tạp thời gian nếu lưu bằng ma trận kề là n^2, bằng danh sách kề n*m và với danh sách kề là n + m.

Nhiệm vụ 3. Cho đồ thị sau đây, bắt đầu từ đỉnh nguồn là s = 5, hãy liệt kê danh sách đỉnh của đồ thị theo thứ tự duyệt BFS.

Nhiệm vụ 4. Đường đi ngắn nhất từ s đến t. UPCODER