#
Các thuật toán tìm kiếm trên đồ thị
Khi giải quyết nhiều bài toán lý thuyết đồ thị, ta phải duyệt qua tất cả các đỉnh của đồ thị đó. Cho nên, ta cần phải sử dụng các thuật toán có khả năng duyệt toàn bộ các đỉnh của đồ thị, gọi chung là thuật toán duyệt đồ thị, hay tìm kiếm trên đồ thị.
Ta sẽ tìm hiểu về 2 thuật toán tìm kiếm khác nhau trên đồ thị:
- Thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS)
- Thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS)
Hai thuật toán mặc dù đều thực hiện việc duyệt đồ thị, nhưng quy trình duyệt và cách áp dụng có đôi phần khác nhau.