Các thuật toán tìm kiếm trên đồ thị và ứng dụng
Rất nhiều thuận toán trên đồ thị được xây dựng trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được viếng thăm đúng một lần. Vì vậy, việc xây dựng những thuật toán cho phép duyệt một cách hệ thống tất cả các đỉnh của đồ thị là ...
Rất nhiều thuận toán trên đồ thị được xây dựng trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được viếng thăm đúng một lần. Vì vậy, việc xây dựng những thuật toán cho phép duyệt một cách hệ thống tất cả các đỉnh của đồ thị là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều tác giả. Những thuật toán như vậy chúng ta sẽ gọi là thuật toán tìm kiếm trên đồ thị. Trong mục này chúng ta sẽ giới thiệu hai thuật toán tìm kiếm cơ bản trên đồ thị: Thuật toán tìm kiếm theo chiều sâu (Depth Firt Search) và Thuật toán tìm kiếm theo chiều rộng (Breadth First Search) và ứng dụng của chúng vào việc giải một số bài toán trên đồ thị.
Trong mục này chúng ta sẽ xét đồ thị vô hướng G=(V,E), với đỉnh n và m cạnh.
Chúng ta sẽ quan tâm đến việc đánh giá hiệu quả của các thuật toán trên đồ thị, màmột trong những đặc trưng quan trọng nhất là độ phức tạp tính toán, tức là số phép toán mà thuật toán cần phải thực hiện trong tình huống xấu nhất được biểu diễn như hàm của kích thước đầu vào của bài toán. Trong các thuật toán trên đồ thị, đầu vào là đồ thị G=(V,E), vì vậy, kích thước của bài toán là số đỉnh n và số cạnh m của đồ thị. Khi đó độ phức tạp tính toán của thuật toán sẽ được biểu diễn như là hàm của hai biến số f(n,m) là số phép toán nhiều nhất cần phải thực hiện theo thuật toán đối với mọi đồ thị n đỉnh và m cạnh. Khi so sánh tốc độ tăng của hai hàm nhận giá trị không âm f(n) và g(n) chúng ta sẽ sử dụng ký hiệu sau:
f(n)=O(g(n))
⇔ tìm được các hằng sô C, N ≥ 0 sao cho
f(n) C g(n) với mọi n ≤ N.
Tương tự như vậy nếu f(n1, n2,. . . ,nk), g(n1, n2,. . . ,nk) là các hàm nhiều biến ta viết
f(n 1 , n 2 ,. . . ,nk) = O(g(n 1 , n 2 ,. . . ,nk))
⇔ tìm được các hằng số C,N >0 sao cho
f(n 1 , n 2 ,. . . ,nk) ≤ C g(n 1 , n 2 ,. . . ,nk) với mọi n 1 , n 2 ,. . . ,nk ≥ N.
Nếu độ phức tạp tính toán của thuật toán là O(g(n)) thì ta sẽ còn nói là nó đòi hỏi thời gian tính cỡ O(g(n)).
Ý tưởng chính của thuật toán có thể trình bày như sau. Ta sẽ 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 tuỳ ý kề với v0 và lặp lại quá trình đối với u. Ở bước tổng quát, giả sử ta đang xét đỉnh v. Nếu như trong số các đỉnh kề với v tìm được đỉnh w là chưa được xét thì ta sẽ xét đỉnh này (nó sẽ trở thành đã xét) và bắt đầu từ nó ta sẽ bắt đầu quá trình tìm kiếm còn nếu như không còn đỉnh nào kề với v là chưa xét thì ta nói rằng đỉnh này đã duyệt xong và quay trở lại tiếp tục tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v (nếu v=v0, thì kết thúc tìm kiếm). Có thể nói nôm na là tìm kiếm theo chiều sâu bắt đầu từ đỉnh v được thực hiện trên cơ sở tìm kiếm theo chiều sâu từ tất cả các đỉnh chưa xét kề với v. Quá trình này có thể mô tả bởi thủ tục đệ qui sau đây:
Procedure DFS(v);
(*tim kiem theo chieu sau bat dau tu dinh v; cac bien Chuaxet, Ke la bien toan cuc*)
Begin
Tham_dinh(v);
Chuaxet[v]:=false;
For u ∈ Ke(v) do
If Chuaxet[u] then DFS(u);
End; (*dinh v da duyet xong*)
Khi đó, tìm kiếm theo chiều sâu trên đồ thị được thực hiện nhờ thuật toán sau:
Begin
(*Initialization*)
for v ∈ V do Chuaxet[v]:=true;
for v ∈ V do
if Chuaxet[v] then DFS(v);
End.
Rõ ràng lệnh gọi SFS(v) sẽ cho phép đến thăm tất cả các đỉnh thuộc cùng thành phần liên thông với đỉnh v, bởi vì sau khi thăm đỉnh là lệnh gọi đến thủ tục DFS đối với tất cả các đỉnh kề với nó. Mặt khác, do mỗi khi thăm đỉnh v xong, bi?n Chuaxet[v] được đặt lại giá trị false nên mỗi đỉnh sẽ được thăm đúng một lần. Thuật toán lần lượt sẽ tiến hành tìm kiếm từ các đỉnh chưa được thăm , vì vậy, nó sẽ xét qua tất cả các đỉnh của đồ thị (không nhất thiết phải là liên thông).
Để đánh giá độ phức tạp tính toán của thủ tục, trước hết nhận thấy rằng 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 ở chương trình chính) là cỡ n. Thủ tục DFS phải thực hiện không quá n lần. Tổng số phép toán cần phaỉ thực hiện trong các thủ tục này là O(n+m), do trong các thủ tục này ta phải xét qua tất cả các cạnh và các đỉnh của đồ thị. Vậy độ phức tạp tính toán của thuật toán là O(n+m).
Thí dụ 1. Xét đồ thị cho trong hình 1 gồm 13 đỉnh, các đỉnh được đánh số từ 1 đến 13 như sau:
Hình 1
Khi đó các đỉnh của đồ thị được đánh số lại theo thứ tự chúng được thăm theo thủ tục tìm kiếm theo chiều sâu mô tả ở trên như hình 2. Giả thiết rằng các đỉnh trong danh sách kề của đỉnh v (Ke(v)) được sắp xếp theo thứ tự tăng dần của chỉ số.
Hình 2. Chỉ số mới (trong ngoặc) của các đỉnh được đánh lại theo thứ tự chúng được thăm trong thuật toán tìm kiếm theo chiều sâu.
Thuật toán tìm kiếm theo chiều sâu trên đồ thị vô hướng trình bày ở trên dễ dàng có thể mô tả lại cho đồ thị có hướng. Trong trường hợp đồ thị có hướng, thủ tcụ DFS(v) sẽ cho phép thăm tất cả các đỉnh u nào mà từ v có đường đi đến u. Độ phức tạp tính toán của htuật toán là O(n+m).
