Không ai đề cập đến yếu tố then chốt trong trường hợp tìm kiếm theo chiều rộng đầu tiên hữu ích: truy cập nút một cách có thể loại bỏ yêu cầu truy cập nút theo cách khác.Trong một số trường hợp, người ta sẽ thực hiện cùng một công việc bất kể thứ tự các nút được truy cập, nhưng BFS sẽ có ít hành động hơn đang chờ xử lý tại một thời điểm nhiều hơn DFS. Trong các trường hợp khác, việc truy cập các nút trong một chuỗi có thể đòi hỏi nhiều công việc hơn các nút khác; các thuật toán ngắn nhất khác nhau được đưa ra như một ví dụ về điều đó. Nếu ghé thăm một nút yêu cầu đến thăm hàng xóm của nó trừ khi nút được biết là có thể truy cập được bằng đường dẫn ngắn hơn nút hiện tại, việc truy cập các nút theo thứ tự chiều rộng đầu tiên thường sẽ dẫn đến các nút được gán đường đi ngắn nhất - hoặc một cái gì đó gần với nó - chuyến thăm đầu tiên của họ. Ngược lại, tìm kiếm theo chiều sâu sẽ khiến nhiều nút được truy cập bằng đường dẫn rất dài lần đầu tiên, sau đó bằng đường dẫn hơi ngắn hơn, đường dẫn ngắn hơn, v.v. yêu cầu tổng số công việc khổng lồ.
BTW, một minh họa đồ họa đẹp về sự khác biệt giữa thuật toán độ sâu đầu tiên và chiều rộng là vùng tràn ngập khu vực, nơi một nút màu trắng tràn ngập bằng cách sơn màu đen và lấp đầy lũ các nước láng giềng. Nếu một cố gắng lấp đầy khu vực hình vuông NxN bắt đầu từ một cornder, một hoạt động chiều sâu đầu tiên sẽ lấp đầy hình vuông trong một chuỗi xoắn ốc hoặc zig-zag, với các hoạt động NxN-1 còn lại trên ngăn xếp. Một điền đầy đủ bề rộng sẽ "đổ" ra khỏi điểm bắt đầu, và có tối đa các hoạt động O (N) đang chờ xử lý, bất kể hình dạng được lấp đầy. BTW, việc lấp đầy lũ lụt trong IBM BASICA đã làm việc theo cách đó (tôi không chắc chắn về QBASIC).
Dường như nó sẽ là một trường hợp cực kỳ nghiêm trọng đối với BFS chiếm ít không gian hơn DFS, xem xét độ phức tạp của không gian của BFS là b^d. –
Sau khi làm mới bản thân mình về những gì b và d thực sự có nghĩa là trong bình luận ở trên của tôi, tôi nhớ rằng mỗi nút có một nút con sẽ là 1^d. Vì vậy, tôi cho rằng chỉ có một nút con * sẽ * là một trường hợp cực đoan. :-) –