Tìm kiếm theo chiều rộng phù hợp với dạng bài toán nào? vì sao?

Đã đăng vào thg 2 9, 9:28 SA 12 phút đọc

Một vấn đề rất quan trọng trong Lý thuyết đồ thị là bài toán duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó, không duyệt lặp lại cũng như không bỏ sót đỉnh nào cả. Vì vậy, ta phải xây dựng được những phép duyệt các đỉnh của đồ thị theo một hệ thống nhất định, những phép duyệt đó gọi là các thuật toán tìm kiếm trên đồ thị.

Có hai giải thuật tìm kiếm trên đồ thị cơ bản: Tìm kiếm theo chiều sâu [Depth First Search - DFS] và Tìm kiếm theo chiều rộng [Breadth First Search - BFS]. Hai giải thuật này có độ phức tạp thuật toán như nhau, nhưng sẽ có những ứng dụng khác nhau và cách cài đặt cũng khác nhau.

Xét bài toán sau: Cho đơn đồ thị vô hướng gồm $n$ đỉnh, $m$ cạnh, danh sách các cạnh được nhập vào theo dạng $[u,v]$ với $u$ và $v$ là các đỉnh thuộc đồ thị $[1\le u\ne v\le n]$. Hãy đưa ra một đường đi từ đỉnh $s$ tới đỉnh $f$ cho trước.

Dưới đây ta sẽ cài đặt hai giải thuật $\text{DFS}$ và $\text{BFS}$ để giải quyết bài toán này. Các cài đặt đều sử dụng danh sách kề, nếu như đề bài thay đổi thành đa đồ thị hay đồ thị có hướng thì chỉ cần sửa đổi một chút trong quá trình nhập dữ liệu.

II. Giải thuật tìm kiếm theo chiều sâu [Depth First Search]

Tư tưởng thuật toán:

• Nhận thấy rằng, mọi đỉnh kề với $s$ đều có thể đến được từ $s$. Với mỗi đỉnh $x$ kề với $s$, thì tất nhiên các đỉnh $y$ kề với $x$ cũng sẽ đến được từ $s$,...Từ đây, ta có thể xây dựng một hàm tìm kiếm $\text{DFS}[u]$ để duyệt các đỉnh kề với đỉnh $u$, hàm này sẽ gọi tiếp tới hàm $\text{DFS}[v]$ với $v$ là đỉnh kề với $u$,...Quá trình tìm kiếm sẽ bắt đầu với lời gọi $\text{DFS}[s]$.
• Để không đỉnh nào bị thăm lại, khi duyệt tới một đỉnh $v$ nào đó, ta sẽ đánh dấu lại nó đã được thăm rồi, bằng cách sử dụng một mảng parvpar_vparv​ là đỉnh liền trước $v$ trong quá trình gọi đệ quy [hay còn gọi là đỉnh cha của đỉnh $v$]. Khi đó, điều kiện để một đỉnh $v$ chưa thăm sẽ là parv=0par_v = 0parv​=0, và khi duyệt tới một đỉnh $v$ kề với đỉnh $u$, ta sẽ gán parv=upar_v=uparv​=u, vừa để thể hiện đỉnh liền trước $v$ trên đường đi từ $s$ tới $v$, vừa để đánh dấu đỉnh $v$ đã thăm rồi.
• Kết thúc giải thuật, đường đi từ $s$ tới $f$ sẽ là:

f←p1=parf←p2=parp1←...←sf \leftarrow p_1=par_f \leftarrow p_2=par_{p_1} \leftarrow ... \leftarrow s f←p1​=parf​←p2​=parp1​​←...←s

Cài đặt:

Hình vẽ dưới đây cho ta minh họa về quá trình duyệt $\text{DFS}$:

Nhận xét:

• Nhờ vào kĩ thuật đánh dấu đường đi, nên hàm $\text{DFS}[u]$ chỉ được gọi không quá $n$ lần.
• Có thể tồn tại nhiều đường đi từ $s$ tới $f,$ nhưng giải thuật $\text{DFS}$ luôn luôn trả về đường đi có thứ tự từ điển nhỏ nhất.
• Quá trình $\text{DFS}$ sẽ cho ta một cây $\text{DFS}$ gốc $s$. Khi đó, tồn tại một quan hệ cha - con trên cây được định nghĩa là: Nếu từ đỉnh $u$ tới thăm đỉnh $v$ $[\text{DFS}[u]$ gọi $\text{DFS}[v]]$ thì $u$ là cha của $v$.

III. Giải thuật tìm kiếm theo chiều rộng [Breadth First Search]

Tư tưởng thuật toán:

• Dựa trên tư tưởng lập ra một thứ tự duyệt các đỉnh, sao cho các đỉnh gần $s$ hơn sẽ luôn luôn được duyệt xong trước các đỉnh xa $s$ hơn. Ví dụ, từ đỉnh $s$ ta thăm các đỉnh kề với nó là x1,x2,...,xkx_1,x_2,...,x_kx1​,x2​,...,xk​. Khi thăm tới x1x_1x1​, sẽ phát sinh việc thăm các đỉnh kề với x1x_1x1​ là x1′,x2′,...,xk′′x'_1 , x'_2,...,x'_{k'}x1′​,x2′​,...,xk′′​. Dĩ nhiên các đỉnh này đều xa $s$ hơn so với x1,x2,...,xkx_1, x_2,..., x_kx1​,x2​,...,xk​, cho nên chúng sẽ chỉ được thăm sau khi toàn bộ các đỉnh x1,x2,...,xkx_1, x_2,..., x_kx1​,x2​,...,xk​ đã được thăm hết.
• Quá trình thăm theo cách này sẽ tạo ra một cây $\text{BFS}$ rộng và hẹp, do đó gọi là tìm kiếm theo chiều rộng.

Thứ tự thăm các đỉnh bằng BFS

• Để xây dựng một thứ tự như vậy, ta sẽ tạo ra một danh sách gồm các đỉnh đang được "chờ" thăm. Tại mỗi bước, thăm đỉnh ở đầu danh sách và thêm toàn bộ các đỉnh kề với đỉnh đó [mà chưa được thăm] vào cuối danh sách, như vậy danh sách sẽ được xây dựng thành các lớp liền nhau, mỗi lớp bao gồm các đỉnh cùng kề với một đỉnh nào đó. Cấu trúc dữ liệu phù hợp nhất để xây dựng danh sách này là hàng đợi [queue].
• Việc truy vết cũng diễn ra tương tự như giải thuật $\text{DFS}$, ta dùng một mảng tracevtrace_vtracev​ để lưu lại đỉnh liền trước với đỉnh $v$ trong quá trình duyệt, và kiêm luôn chức năng đánh dấu đỉnh $v$ đã được thăm hay chưa.

Cài đặt: