Sự khác biệt giữa BFS và DFS

BFS vs DFS

Breadth First Search (còn được gọi là BFS) là một phương pháp tìm kiếm được sử dụng để mở rộng tất cả các nút của một biểu đồ cụ thể. Nó hoàn thành nhiệm vụ này bằng cách tìm kiếm mọi giải pháp duy nhất để kiểm tra và mở rộng các nút này (hoặc kết hợp các chuỗi trong đó). Như vậy, BFS không sử dụng thuật toán heuristic (hoặc thuật toán tìm kiếm giải pháp thông qua nhiều kịch bản). Sau khi tất cả các nút được lấy, chúng được thêm vào hàng đợi được gọi là hàng đầu vào, ra trước. Các nút chưa được khám phá sẽ được 'lưu trữ' trong một thùng chứa được đánh dấu 'mở'; một khi được khám phá, chúng được chuyển đến một container được đánh dấu là 'đã đóng'.

Depth First Search (còn được gọi là DFS) là một phương pháp tìm kiếm đào sâu vào nút con của tìm kiếm cho đến khi đạt được mục tiêu (hoặc cho đến khi có một nút mà không có bất kỳ hoán vị hoặc 'trẻ em' nào khác). Sau khi tìm thấy một mục tiêu, các backtracks tìm kiếm đến một nút trước đó đã đi cùng với một giải pháp, lặp lại quá trình cho đến khi tất cả các nút đã được tìm kiếm thành công. Do đó, các nút tiếp tục được đặt sang một bên để thăm dò thêm - điều này được gọi là thực hiện không đệ quy.

Các tính năng của BFS là độ phức tạp về không gian và thời gian, tính đầy đủ, bằng chứng về tính đầy đủ và tính tối ưu. Độ phức tạp không gian đề cập đến tỷ lệ số lượng nút ở mức sâu nhất của tìm kiếm. Độ phức tạp thời gian đề cập đến lượng 'thời gian' thực tế được sử dụng để xem xét mọi đường dẫn mà một nút sẽ thực hiện trong tìm kiếm. Về cơ bản, tính đầy đủ là một tìm kiếm tìm ra giải pháp trong biểu đồ bất kể đó là loại biểu đồ nào. Bằng chứng về tính đầy đủ là mức độ nông nhất mà tại đó mục tiêu được tìm thấy trong một nút ở độ sâu xác định. Cuối cùng, sự tối ưu đề cập đến một BFS không có trọng số - đó là biểu đồ được sử dụng cho chi phí bước đơn vị.

Một DFS là đầu ra tự nhiên nhất bằng cách sử dụng một cây bao trùm - là một cây được tạo thành từ tất cả các đỉnh và một số cạnh trong một đồ thị vô hướng. Trong đội hình này, đồ thị được chia thành ba lớp: Chuyển tiếp các cạnh, chỉ từ một nút đến một nút con; các cạnh sau, chỉ từ một nút đến một nút trước đó; và các cạnh chéo, không làm một trong hai.

Tóm lược:

1. BFS tìm kiếm mọi giải pháp đơn lẻ trong biểu đồ để mở rộng các nút của nó; một DFS đào sâu trong một nút con cho đến khi đạt được mục tiêu.

2. Các tính năng của BFS là độ phức tạp về không gian và thời gian, tính đầy đủ, bằng chứng về tính đầy đủ và tính tối ưu; đầu ra tự nhiên nhất cho DFS là một cây bao trùm với ba lớp: cạnh trước, cạnh sau và cạnh chéo.