Trong giải quyết các bài toán tìm kiếm, thì 2 thuật toán tìm kiếm theo chiều sâu - DFS và theo chiều rộng - BFS rất hay được ứng dụng, với mỗi yêu cầu khác nhau ta nên sử dụng một thuật toán thích hợp để đưa ra được kết quả tối ưu nhất. Vậy nên, hôm nay mình xin chia sẻ về các dạng toán thường gặp sử dụng đến 2 thuật toán tìm kiếm này.
1. Bài toán tìm khoảng cách ngắn nhất giữa 2 đỉnh trong cùng một tập liên thông (không trọng số): BFS.
2. Bài toán topology sort: DFS.
3. Bài toán tin ra chu trình của đồ thị: DFS.
4. Bài toán kiểm tra đồ thị có chu trình không: BFS và DFS đều được.
5. Bài toán kiểm tra 2 đỉnh có liên thông không: BFS và DFS đều được.
6. Bài toán in đường đi giữa 2 đỉnh: BFS và DFS đều được.
7. Đếm số lượng phần tử của 1 tập liên thông: BFS và DFS đều được.
8. Đếm số lượng thành phần liên thông: BFS và DFS đều được.
9. Bài toán kiểm tra tập đã cho có phải là tập 2 thành phần không(đồ thị 2 phía, tô màu đồ thị): BFS và DFS đều được.
10.Tìm cây khung nhỏ nhất trong đồ thị không trọng số: BFS và DFS đều được.
....
Trên đây mình đã chia sẻ một số dạng toán sử dụng thuật toán BFS và DFS, bài sau mình sẽ chia sẻ một số bài toán ví dụ cụ thể cho từng dạng.
1. Bài toán tìm khoảng cách ngắn nhất giữa 2 đỉnh trong cùng một tập liên thông (không trọng số): BFS.
2. Bài toán topology sort: DFS.
3. Bài toán tin ra chu trình của đồ thị: DFS.
4. Bài toán kiểm tra đồ thị có chu trình không: BFS và DFS đều được.
5. Bài toán kiểm tra 2 đỉnh có liên thông không: BFS và DFS đều được.
6. Bài toán in đường đi giữa 2 đỉnh: BFS và DFS đều được.
7. Đếm số lượng phần tử của 1 tập liên thông: BFS và DFS đều được.
8. Đếm số lượng thành phần liên thông: BFS và DFS đều được.
9. Bài toán kiểm tra tập đã cho có phải là tập 2 thành phần không(đồ thị 2 phía, tô màu đồ thị): BFS và DFS đều được.
10.Tìm cây khung nhỏ nhất trong đồ thị không trọng số: BFS và DFS đều được.
....
Trên đây mình đã chia sẻ một số dạng toán sử dụng thuật toán BFS và DFS, bài sau mình sẽ chia sẻ một số bài toán ví dụ cụ thể cho từng dạng.
