Thuật Toán Depth First Search

+ 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:

– 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ớ.

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.

+ Và chương trình phải đáp ứng các yêu cầu như sau.

=> Duyệt được toàn bộ thông tin các phòng ban và in ra văn bản

=> Nhập tên một nhân viên bất kỳ, hay mã id, hay một thông số nào đó,

thì phải tìm được cá nhân đó thuộc phòng ban nào.

Các bạn hãy thử demo xem.

TPham