Khi nào sử dụng DFS tốt hơn BFS?
Khi nào sử dụng DFS tốt hơn BFS?
DFS phù hợp: phát hiện chu trình, sắp xếp topo, tìm thành phần liên thông/ liên thông mạnh (Tarjan, Kosaraju), giải mê cung/ backtracking (Sudoku, N-Queens), duyệt cây, kiểm tra hai phía, tìm cầu/ điểm khớp, đếm số đảo. BFS phù hợp: đường đi ngắn nhất trong đồ thị không trọng số, duyệt theo tầng, lan truyền theo lớp (mạng xã hội: bạn bè bậc k), web crawler theo độ sâu, Flood fill khoảng cách, BFS đa nguồn (rotting oranges).
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.