[java] So Sánh DFS và BFS trong thuật toán tìm kiếm

Khái niệm

DFS (Tìm kiếm Độ sâu thứ nhất) và BFS (Tìm kiếm Breadth Đầu tiên) là các thuật toán tìm kiếm được sử dụng cho đồ thị và cây. Khi bạn có cây hoặc đồ thị được sắp xếp, giống như BST, bạn có thể dễ dàng tìm kiếm cấu trúc dữ liệu để tìm nút mà bạn muốn. Tuy nhiên, khi đưa ra một cây hoặc đồ thị không có thứ bậc, thuật toán tìm kiếm BFS và DFS có thể hữu ích để tìm thấy những gì bạn đang tìm kiếm. Quyết định chọn một trong những khác cần được dựa trên loại dữ liệu mà một trong những là làm việc với.

Trong một tìm kiếm đầu tiên, bạn bắt đầu từ nút gốc, và sau đó quét từng nút ở mức đầu tiên bắt đầu từ nút trái, di chuyển về phía bên phải. Sau đó, bạn tiếp tục quét mức thứ hai (bắt đầu từ bên trái) và mức thứ ba, v.v ... cho đến khi bạn đã quét tất cả các nút hoặc cho đến khi bạn tìm thấy nút thực mà bạn đang tìm kiếm. Trong một BFS, khi vượt qua một mức độ, chúng ta cần một số cách để biết được các nút nào đi qua khi chúng ta đạt đến cấp độ tiếp theo. Cách này được thực hiện bằng cách lưu trữ các con trỏ tới các nút con của cấp độ trong khi tìm kiếm mức đó. Các con trỏ được lưu trữ trong hàng đợi FIFO (First-In-First-Out). Điều này, lần lượt, có nghĩa là BFS sử dụng một lượng lớn bộ nhớ vì chúng ta phải lưu trữ các con trỏ.

Ví dụ về BFS

Dưới đây là một ví dụ về một BFS sẽ như thế nào. Các con số đại diện cho thứ tự trong đó các nút được truy cập trong một BFS:

Trong một tìm kiếm sâu, bạn bắt đầu từ gốc, và đi theo một trong các chi nhánh của cây càng nhiều càng tốt cho đến khi tìm thấy nút hoặc tìm nút nào đó (nút không có con). Nếu bạn nhấn nút lá, sau đó bạn tiếp tục tìm kiếm ở tổ tiên gần nhất với trẻ em chưa được khám phá.

Ví dụ về DFS

Đây là một ví dụ về một DFS sẽ như thế nào. Các con số đại diện cho thứ tự trong đó các nút được truy cập trong một DFS:

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

So sánh BFS và DFS, lợi thế lớn của DFS là nó có yêu cầu bộ nhớ thấp hơn nhiều so với BFS, bởi vì nó không cần thiết để lưu trữ tất cả các con con trỏ ở mỗi cấp. Tùy thuộc vào dữ liệu và những gì bạn đang tìm kiếm, hoặc DFS hoặc BFS có thể là thuận lợi.

Ví dụ, nếu có một cây gia đình nếu ai đó đang tìm kiếm ai đó trên cây mà vẫn còn sống, thì có thể an toàn khi cho rằng người đó sẽ ở dưới đáy của cây. Điều này có nghĩa là một BFS sẽ mất một thời gian dài để đạt được mức độ cuối cùng. Một DFS, tuy nhiên, sẽ tìm thấy mục tiêu nhanh hơn. Nhưng, nếu một người đang tìm kiếm một người trong gia đình đã chết cách đây rất lâu, người đó sẽ ở gần đỉnh cây. Sau đó, một BFS thường sẽ nhanh hơn DFS. Vì vậy, những lợi thế của một trong hai thay đổi tùy thuộc vào dữ liệu và những gì bạn đang tìm kiếm.

Cám ơn các bạn đã quan tâm theo dõi.

Source : programmerinterview