Depth First Search là gì

Giải thuật tìm kiếm theo chiều sâu là gì ?

Giải thuật tìm kiếm theo chiều sâu [Depth First Search – viết tắt là DFS], còn được gọi là giải thuật tìm kiếm ưu tiên chiều sâu, là giải thuật duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị và sử dụng stack [ngăn xếp] để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kỳ vòng lặp nào. Giải thuật tiếp tục cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước.

Trong hình minh họa trên, giải thuật tìm kiếm theo chiều sâu đầu tiên duyệt từ các đỉnh A tới B tới C tới D sau đó tới E, sau đó tới F và cuối cùng tới G. Giải thuật này tuân theo qui tắc sau:

• Qui tắc 1: Duyệt tiếp tới đỉnh liền kề mà chưa được duyệt. Đánh dấu đỉnh mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào trong một ngăn xếp [stack].

• Qui tắc 2: Nếu không tìm thấy đỉnh liền kề, thì lấy một đỉnh từ trong ngăn xếp [thao tác pop up]. [Giải thuật sẽ lấy tất cả các đỉnh từ trong ngăn xếp mà không có các đỉnh liền kề nào]

• Qui tắc 3: Lặp lại các qui tắc 1 và qui tắc 2 cho tới khi ngăn xếp là trống.

Bảng dưới đây minh họa các qui tắc với hình ví dụ trên:

BướcDuyệtMiêu tả1.Khởi tạo ngăn xếp [stack]2.Đánh dấu đỉnh S là đã duyệt và đặt đỉnh này vào trong ngăn xếp. Tìm kiếm bất kỳ đỉnh liền kề nào mà chưa được duyệt từ đỉnh S. Chúng ta có 3 đỉnh và chúng ta có thể lấy bất kỳ đỉnh nào trong số chúng. Ví dụ, chúng ta lấy đỉnh A theo thứ tự chữ cái.3.Đánh dấu đỉnh A là đã duyệt và đặt vào trong ngăn xếp. Tìm kiếm bất kỳ đỉnh liền kề nào với đỉnh A. Cả S và D đều là hai đỉnh liền kề A nhưng chúng ta chỉ quan tâm về đỉnh chưa được duyệt.4.Duyệt đỉnh D, đánh dấu đỉnh này là đã duyệt và đặt vào trong ngăn xếp. Ở đây, chúng ta có B và C là hai đỉnh kề với D và cả hai đều là chưa được duyệt. Chúng ta sẽ chọn theo thứ tự chữ cái một lần nữa.5.Chọn B, đánh dấu là đã duyệt và đặt vào trong ngăn xếp. Ở đây B không có bất kỳ đỉnh liền kề nào mà chưa được duyệt. Vì thế chúng ta lấy B ra khỏi ngăn xếp.6.Kiểm tra phần tử trên cùng của ngăn xếp để trở về nút đã duyệt trước đó và kiểm tra xem đỉnh này có đỉnh nào liền kề mà chưa được duyệt hay không. Ở đây, chúng ta tìm thấy đỉnh D nằm ở trên cùng của ngăn xếp.7.Chỉ có một đỉnh liền kề với D mà chưa được duyệt, đó là đỉnh C. Chúng ta duyệt C, đánh dấu là đã duyệt và đặt vào trong ngăn xếp.

Vì C không có bất kỳ đỉnh nào liền kề mà chưa được duyệt, chúng ta tiếp tục lấy các đỉnh từ trong ngăn xếp để tìm xem có còn bất kỳ đỉnh nào liền kề mà chưa được duyệt hay không. Trong ví dụ này là không có, và chúng ta vẫn tiếp tục cho tới khi ngăn xếp là trống.

Trên đây là phần giới thiệu và minh họa cho giải thuật tìm kiếm theo chiều sâu. Để tìm hiểu code đầy đủ của giải thuật tìm kiếm theo chiều sâu trong ngôn ngữ C, mời bạn click chuột vào chương: Tìm kiếm theo chiều sâu trong C.

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team //www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền //www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.

cấu trúc dữ liệu và giải thuật, giải thuật c++, giải thuật lập trình, học thuật toán, thuật toán c++, thuật toán code c++, thuật toán depth first search, thuật toán lập trình, tìm kiếm chiều sâu 5 min read

 

Bài hôm nay chúng ta cùng tìm hiểu về thuật toán  Depth First Search [Tìm kiếm theo chiều sâu]1. Kiến thức cơ bản về thuật toán DFS.

+ Depth First Search là một thuật toán duyệt hoặc tìm kiếm một phần tử trên một cấu trúc dữ liệu dạng cây hay một đồ thị.

+ Bắt đầu đi từ một đỉnh của cây, sau đó từ đỉnh đó tìm ra node đầu tiên và cứ tìm các note tiếp theo

cho đến khi không đi được nữa, thì lại quay về node trước đó và tìm sang node bên cạnh để đi tiếp.

 

Như vậy thứ tự đi trong hình minh họa ở trên như sau:

• Bắt đầu từ 1 => 2 => 3 => 4  => hết đường đi
• Quay lại 3 => 5                             => hết đường đi
• Tiếp tục từ 3  quay lại 2 => 6   => hết đường đi
• Quay lại 2 => quay lại 1 => 7     => hết đường đi
• Tiếp tục từ 1 => 8 => 9=> 10   => hết đường đi
• Quay lại 9 => 11                            => hết đường đi
• Tiếp tục 9=> quay lại 8 => 12  => hết đường đi
• Quay lại 8 => quay lại 1              => hết đường => KẾT THÚC.

2. Các tính chất depth first search.

– Là cấu trúc dữ liệu dạng đồ thị, hay dạng cây.

– Độ phức tạp thời gian là: O[|V| + |E|]  V là số đỉnh duyệt qua và E là số cạnh duyệt qua

– Độ phức tạp không gian là O[|V|]. Số đỉnh là số phần tử cần lưu trữ vào bộ nhớ.

3 Thực hành DFS.

Thực hiện được hai bước cho bài toán thực hành thuật toán depth first search.

+ Xây dựng được cấu trúc dữ liệu dạng cây, với phần tử cha là phần tử đầu tiên của cây.

+ Viết hàm tìm kiếm, duyệt các phần tử bắt đầu từ phần tử cha ở trên.

a. Áp dụng với bài toán đơn giản cho hình minh họa ở trên.

+ Node là một đối tượng chung, và mỗi node có thể trỏ đến nhiều node khác là kiểu dữ liệu như nó.

=> xây dựng node là một class, và trong nó lại lưu trữ một list các đối tượng chính nó.

xây dựng một class như sau:

Định nghĩa hàm AddChild để thêm node vào.

Viết hàm duyệt case

Xây dựng hàm tạo cây nhị phân lưu trữ dữ liệu.

 

Trong hàm main chúng ta chỉ việc gọi.

int main[int argc, _TCHAR* argv[]]
{
   DemoDFSTree[];
   return 0;
}

Ok. Như vậy là chúng ta đã có thể demo được thuật toán DFS bằng code c++ với bài toán cơ bản nhất.

 

b. Áp dụng vào thực tế dự án, mức độ nâng cao.

Khi áp dụng vào bài toán thực tế, thì nó không đơn giản chỉ là lưu dữ liệu thuần túy kiểu số nguyên hay số thực,

mà thuật toán sẽ được áp dụng cho các dạng dữ liệu bất kỳ, các loại đối tượng bất kỳ.

Tôi ví dụ hình minh họa như sau:

+ Bài toán đặt ra là xây dựng mô hình quản lý nhân viên 1 công ty phần mềm theo cấu trúc dạng cây như trên.