Ưu tiên tìm kiếm chiều sâu trên bề rộng tìm kiếm đầu tiên hoặc ngược lại

Question

Tôi đã nghiên cứu hai thuật toán truyền tải đồ thị, tìm kiếm chiều sâu và tìm kiếm đầu tiên. làm thế nào để lựa chọn giữa hai.Tôi có nghĩa là một trong những hiệu quả hơn so với lý do khác hoặc lý do tại sao tôi sẽ chọn một trong những khác trong một kịch bản cụ thể?

Cảm ơn bạn

Answer 1

Sự khác biệt chính đối với tôi có phần lý thuyết. Nếu bạn có một đồ thị có kích thước vô hạn thì DFS sẽ không bao giờ tìm thấy một phần tử nếu nó tồn tại bên ngoài đường dẫn đầu tiên mà nó chọn. Nó về cơ bản sẽ tiếp tục đi xuống con đường đầu tiên và sẽ không bao giờ tìm thấy nguyên tố. BFS cuối cùng sẽ tìm thấy phần tử.

Nếu kích thước của đồ thị là hữu hạn, DFS có thể tìm thấy phần tử outlier (khoảng cách lớn hơn giữa gốc và mục tiêu) nhanh hơn nơi BFS sẽ tìm thấy phần tử gần hơn nhanh hơn. Ngoại trừ trong trường hợp DFS chọn đường dẫn của phần tử nông.

Answer 2

Nói chung, BFS tốt hơn cho các vấn đề liên quan đến việc tìm đường đi ngắn nhất hoặc các vấn đề liên quan đến phần nào đó. Bởi vì ở đây bạn đi từ một nút đến tất cả các nút liền kề với nó và do đó bạn có hiệu quả di chuyển từ chiều dài đường dẫn một đến chiều dài đường dẫn hai và cứ thế.

Trong khi DFS ở đầu kia giúp nhiều hơn trong các vấn đề kết nối và cũng trong việc tìm chu kỳ trong đồ thị (mặc dù tôi nghĩ bạn có thể tìm thấy chu kỳ với một chút sửa đổi của BFS quá). Xác định kết nối với DFS là tầm thường, nếu bạn gọi thủ tục khám phá hai lần từ thủ tục DFS, thì biểu đồ bị ngắt kết nối (điều này là dành cho một đồ thị vô hướng). Bạn có thể thấy thuật toán thành phần được kết nối mạnh mẽ cho một biểu đồ được chỉ dẫn ở đây, đây là một sửa đổi của DFS. Một ứng dụng khác của DFS là phân loại topo.

Đây là một số ứng dụng của cả hai thuật toán:

DFS:

Khả năng kết nối
thành phần liên thông mạnh
tôpô Sorting

BFS:

Shortest Path (Dijkstra là một số những gì sửa đổi BFS).
Kiểm tra xem biểu đồ có phải là Bipartitie hay không.

Answer 3

Đối với cây hoàn chỉnh/hoàn hảo, DFS lấy một khoảng không tuyến tính tương ứng với độ sâu của cây trong khi BFS lấy một khoảng không gian mũ theo độ sâu của cây. Điều này là do BFS số lượng nút tối đa trong hàng đợi tỉ lệ thuận với số lượng nút trong một mức của cây. Trong DFS, số lượng nút tối đa trong ngăn xếp tỷ lệ thuận với độ sâu của cây.

Answer 4

Khi duyệt qua biểu đồ được kết nối nhiều lần, thứ tự các nút được truyền qua có thể ảnh hưởng rất lớn (theo nhiều đơn vị độ lớn) số lượng nút sẽ được theo dõi bằng phương pháp di chuyển ngang. Một số loại thuật toán sẽ được ồ ạt tốt hơn khi sử dụng bề rộng đầu tiên; những người khác sẽ được ồ ạt tốt hơn khi sử dụng tìm kiếm chuyên sâu.Tại một cực đoan, thực hiện tìm kiếm theo chiều sâu trên cây nhị phân với N nút lá yêu cầu phương thức di chuyển theo dõi các nút lgN trong khi tìm kiếm theo chiều rộng sẽ yêu cầu theo dõi ít ​​nhất N/2 nút (vì nó có thể quét tất cả các nút khác trước khi quét bất kỳ nút lá nào, ngay trước khi quét nút lá đầu tiên, nó sẽ gặp N/2 của các nút cha của các lá phải được theo dõi riêng vì không có tham chiếu nào trong số chúng) . Mặt khác, làm ngập lụt trên lưới NxN với một phương pháp, nếu điểm ảnh của nó chưa được tô màu, màu sắc mà điểm ảnh và sau đó tràn ngập các nước láng giềng của nó sẽ yêu cầu hấp thụ O (N) tọa độ pixel nếu sử dụng tìm kiếm theo chiều rộng, nhưng tọa độ pixel O (N^2) nếu sử dụng độ sâu đầu tiên. Khi sử dụng tìm kiếm rộng đầu tiên, sơn sẽ có vẻ "trải ra", bất kể hình dạng được vẽ; khi sử dụng thuật toán độ sâu đầu tiên để vẽ hình xoắn ốc hình chữ nhật, mỗi đường thẳng ở một bên và bị răng cưa ở mặt kia (mặt phải thẳng và lởm chởm phụ thuộc vào thuật toán chính xác được sử dụng), tất cả các phần thẳng sẽ được vẽ trước bất kỳ loại răng cưa nào, có nghĩa là hệ thống phải theo dõi vị trí của từng thùng riêng biệt.

Answer 5

Trong một số ngôn ngữ, một BFS là một lựa chọn tốt hơn một chút vì việc thực hiện đơn giản nhất của DFS là đệ quy, trong đó giới thiệu một trên cao, và cũng có thể gây ra mã của bạn để đạt giới hạn kích thước ngăn xếp cho đồ thị lớn. Lợi thế rõ ràng (và ứng dụng) của BFS là rằng trong đồ thị không có trọng số, nó có thể được sử dụng để xây dựng một đường đi ngắn nhất từ ​​u đến v.Điều này có rất nhiều ứng dụng - ví dụ, bạn có thể tính số lần di chuyển nhỏ nhất cần thiết để giải quyết một câu đố nhất định bằng cách chạy BFS trên không gian trạng thái của nó. BFS thậm chí có thể cung cấp cho bạn khoảng cách ngắn nhất từ ​​ một đỉnh u đến tất cả các đỉnh khác trong biểu đồ: cho mỗi đỉnh, chỉ cần nhớ cạnh đã được sử dụng để phát hiện ra nó.