Thuật Toán Breadth First Search
Bài hôm nay chúng ta cùng tìm hiểu về thuật toán tìm Breadth First Search (tìm kiếm theo chiều rộng)
1. Kiến thức cơ bản về thuật toán BFS.
+Breadth 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ị.
+ Nó khác với DFS đó là nó sẽ ưu tiên theo chiều ngang, nghĩa là duyệt từ trái qua phải hết rồi mới duyệt tiếp xuống dưới cho từng phần tử
Như vậy thứ tự đi trong hình minh họa ở trên như sau:
- Bắt đầu từ 1 => 2 => 7 => 8 => hết node ngang.
- Tiếp tục 2 => 3 => 6 hết node ngang.
- Bắt đầu 7 => không có node ngang.
- Tiếp tục 8=>9 => 12 hết node ngang
- Bắt đầu 3 => 4 => 5 => hết node ngang
- Tiếp tục 6 => không có node ngang
- Bắt đầu 9 => 10=> 11 hết node ngang
- Tiếp tục 12 => không có node ngang
- Bắt đầu 4 => hết node
- Tiếp tục 5 => hết node
- Bắt đầu 10 => hết node
- Tiếp tục 11 => hết node
2. Các tính chất thuật toán breath first search.
– Sử dụng cấu trúc dữ liệu hàng đợi để lưu trữ node.
– 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 Breath First Search.
Thực hiện được hai bước cho bài toán thực hành thuật toán Breath 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.
KẾT QUẢ CHÚNG TA CẦN CÓ ĐƯỢC ĐÓ LÀ HIỆN THỊ: 1 – 2 7 8 – 3 6 9 12 – 4 5 10 11.
+ 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ó.
list lưu trữ các node chính là một cấu trúc dữ liệu kiểu Hàng Đợi.
xây dựng một class như sau:
Định nghĩa hàm AddChild để thêm node và hàm tìm kiếm duyệt node, hàm in dữ liệu
Xây dựng hàm tạo cây nhị phân lưu trữ dữ liệu.
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 bài toán hướng đối tượng. Giống như DFS.
Vẫn là hình minh họa như DFS, nhưng các bạn sẽ thấy,
cách duyệt của BFS sẽ là duyệt tất cả các phòng ban, sau đó mới duyệt các bộ phận của từng phòng ban.
Khác với DFS là duyệt từng phòng ban và duyệt hết các bộ phận phòng ban rồi mới sang phòng ban kết tiếp.
Từ video thực hành bài toán nâng cao của DFS mà tôi đã thực hành trên video, các bạn thử áp dụng với BFS.
