Ở đây chúng ta xem các ứng dụng khác nhau của thuật toán DFS và BFS trên đồ thị.
Ứng dụng của DFS (Depth First Search)
- Thực hiện DFS trên đồ thị không trọng số sẽ tạo ra cây khung nhỏ nhất cho cây đường đi ngắn nhất mọi cặp (all pair shortest path tree).
- Phát hiện chu trình (cycle) trong đồ thị bằng DFS. Nếu gặp một back-edge trong DFS, chắc chắn có chu trình.
- Tìm đường đi giữa hai đỉnh u và v cho trước bằng DFS.
- Sắp xếp topo (topological sorting) dùng để lên lịch công việc từ các phụ thuộc giữa các công việc. Có thể làm bằng DFS.
- Tìm thành phần liên thông mạnh (strongly connected components) bằng DFS. Nếu có đường đi từ mỗi đỉnh đến mọi đỉnh khác, đó là liên thông mạnh.
Ứng dụng của BFS (Breadth First Search)
- Trong mạng peer-to-peer như BitTorrent, BFS dùng để tìm tất cả nút láng giềng (neighbor nodes).
- Crawler của công cụ tìm kiếm dùng BFS để xây dựng chỉ mục. Từ trang nguồn, tìm tất cả liên kết để lấy trang mới.
- Hệ thống điều hướng GPS dùng BFS để tìm địa điểm lân cận.
- Trong mạng, khi muốn phát sóng (broadcast) gói tin, dùng thuật toán BFS.
- Thuật toán tìm đường (path finding) dựa trên BFS hoặc DFS.
- BFS dùng trong thuật toán Ford-Fulkerson để tìm luồng cực đại (maximum flow) trong mạng.