Thuật Toán Tìm Kiếm Theo Chiều Sâu - [Giáo Trình] Phân Tích Thiết Kế ...

4.1. Giới thiệu thuật toán

Ý tưởng thuật toán: Thuật toán toán tìm kiếm theo chiều sâu (Deapth First Seach - DFS) tìm

kiếm sâu dần trên đồ thị chừng nào còn có thể. Ý tưởng của DFS như sau: Bắt đầu tìm kiếm từ một đỉnh v0 nào đó của đồ thị. Sau đó chọn u là một đỉnh kề với v0 vàlặp lại quá trình như thế đối với đỉnh u. Giả sử ta đang xét đỉnh v ở một bước nào đó, khi đó các cạnh đến được đỉnh v sẽ chưa được thăm cho đến khi nào v còn cạnh (đi ra từ nó) chưa được thăm. Khi tất cả các cạnh của v đã được thăm, thì ta nói rằng đỉnh v đã được duyệt xong và quay trở lại tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v. Quá trình này tiếp tục cho đến khi v = v0 thì kết thúc nghĩa là tất cả các cạnh của đồ thị đã được thăm.

Đồ thị con trước đó: Trong thuật toán tìm kiếm theo chiều sâu, với u là một đỉnh đã được thăm, thì mỗi khi một đỉnh v thuộc danh sách kề của u được thăm, thuật toán sẽ đánh dấu bằng cách đặt trước v một trường π(v) có giá trị là u. Khác với thuật toán tìm kiếm theo chiều rộng (toàn bộ đồ thị con trước đó - predecessor subgraph – là đồ thị tạo ra khi thăm các đỉnh trước đó trong quá

thị con trước đó có thể xác định nhiều cây tìm kiếm khác nhau và có thể được lặp lại từ nhiều đỉnh khác nhau. Vì vậy đồ thị con trước đó trong thuật toán tìm kiếm theo chiều sâu được định nghĩa hơi khác một chút so với trong thuật toán tìm kiếm theo chiều rộng. Ta định nghĩa như sau:

Gπ = (V, Eπ) trong đó Eπ= { ( π[v], v) : v ∈ V và π[v] # Nil }

Đồ thị con trước đó trong thuật toán tìm kiếm theo chiều sâu sẽ xác định một rừng cây tìm kiếm theo chiều sâu (a depth-first forest ) là tập hợp của các cây tìm kiếm theo chiều sâu (deepth- first trees ). Các cạnh thuộc Eπ gọi là các cạnh của cây (tree edges).

Tô màu theo chiều sâu: Trong thuật toán tìm kiếm theo chiều sâu, các đỉnh của đồ thị có thể được tô màu để mô tả trạng thái của nó tại mỗi thời điểm. Các đỉnh ban đầu chưa được thăm sẽ được khởi tạo là màu trắng, khi được thăm sẽ tô màu xám và tô màu đen khi đã duyệt xong. Giải thuật tô màu trên sẽ đảm bảo chính xác mỗi đỉnh chỉ được duyệt một lần, vì vậy mà các cây tìm kiếm theo chiều sâu phân biệt được với nhau.

Thứ tự duyệt đến và duyệt xong: Bên cạnh việc tạo ra một rừng cây tìm kiếm theo chiều sâu, thuật toán tìm kiếm theo chiều sâu còn gán cho mỗi đỉnh một tem thời gian (timestamps). Mỗi đỉnh v sẽ có 2 tem thời gian:

• Khi đỉnh v bắt đầu được thăm lần đầu tiên, ta nói rằng v được duyệt đến và được gán tem thứ nhất d[v] (được tô màu xám).

• Khi chuẩn bị khi lùi về đỉnh trước đỉnh v, tức là các đỉnh trong danh sách kề của v đã được duyệt, ta nói rằng đỉnh v được duyệt xong, và v được gán tem thứ hai f[v] (tô màu đen).

Các tem thời gian này giúp ích rất nhiều cho việc mô tả quá trình thực hiện các bước trong thuật toán tìm kiếm theo chiều sâu; được sử dụng nhiều trong các thuật toán đồ thị như tìm thành phần liên thông mạnh, thuật toán sắp xếp topo.

4.2. Thủ tục tìm kiếm theo chiều sâu

Thủ tục DFS dưới đây khởi tạo mọi đỉnh của đồ thị có màu trắng, mỗi đỉnh đều chưa có đỉnh đi trước (π(u) = nill) và khởi tạo biến thời gian bằng 0. Khi đồ thì không liên thông thì đoạn trình tiếp theo (dòng 5, 6, 7) sẽ lần lượt tìm các cây tìm kiếm theo chiều sâu bằng thủ tục DFS-Visit(u) trong đó u là đỉnh gốc của cây (chưa thăm - màu trắng).

procedure DFS(G)

1 begin for u ∈ V[G] do begin

2 color[u] ← WHITE; 3 π [u] ← NIL; end; 4 time ← 0;

6 if color[u] = WHITE then

7 DFS-Visit(u); end;

procedure DFS-Visit(u)

1 begin color[u] ←GRAY {Trong khi mọi đỉnh v kề u chưa được thăm} 2 d[u] ← (time ← time + 1);

3 for v ∈ Adj[u] do {thăm cạnh (u,v)} 4 if color[v] = WHITE then

5 begin π [v] ← u; 6 DFS-Visit(v); end;

7 color[u] ← BLACK {Tô màu đen cho đỉnh u khi đã duyệt xong} 8 f[u] ← (time ← time + 1);

end;

Tại mỗi lần gọi thủ tục DFS-Visit(u):

ƒ Đỉnh u ban đầu đang được tô màu trắng.

ƒ Khi thực hiện, dòng 1 sẽ tô màu xám cho đỉnh u

ƒ Dòng 2 ghi lại thời điểm đỉnh u bắt đầu được thăm lần đầu tiên vào biến time sau khi tăng nó lên 1.

ƒ Dòng 3-6 kiểm tra các đỉnh v kề với đỉnh u và thực hiện thăm v một cách đệ quy nếu nó vẫn là đỉnh trắng. Với mỗi đỉnh v được xét tại dòng 3, ta nói rằng cạnh (u,v) đã được thăm trong thuật toán tìm kiếm theo chiều sâu .

ƒ Khi tất cả các cạnh đi từ u đã được thăm, dòng 7-8 sẽ tô màu đen cho đỉnh u và ghi lại thời điểm đỉnh u đã duyệt xong trong biến f[u].

4.3. Đánh giá độ phức tạp thuật toán DFS và DFS-Visit

Thủ tục DFS: Số phép toán cần thực hiện trong hai chu trình của thuật toán (hai vòng for-do ở

dòng 1-2 và 5-7) là cỡ O(V).

Thủ tục DFS-Visit: sẽ được gọi chính xác chỉ một lần cho mỗi đỉnh thuộc V và mỗi lần thực

hiện không quá ⎥A[v]| phép toán. Trong đó : ∑ ∈ = V v E O v A[ ] ( )

nghĩa là tổng số phép toán cần thực hiện tại các dòng 2-5 của thủ tục DFS-Visit là O(E). Vì vậy độ phức tạp tính toán của thủ tục DFS sẽ là O (V+E).