BFS và DFS – Sự khác biệt giữa chúng
Sarah Chen
Sự khác biệt chính giữa BFS và DFS
- BFS tìm đường đi ngắn nhất tới đích, trong khi DFS đi đến cuối cây con, sau đó quay lại.
- Dạng đầy đủ của BFS là Tìm kiếm theo chiều rộng, trong khi dạng đầy đủ của DFS là Tìm kiếm theo chiều sâu.
- BFS sử dụng hàng đợi để theo dõi vị trí tiếp theo sẽ ghé thăm. trong khi DFS sử dụng ngăn xếp để theo dõi vị trí tiếp theo sẽ ghé thăm.
- BFS duyệt theo cấp độ cây, trong khi DFS duyệt theo độ sâu của cây.
- BFS được triển khai bằng danh sách FIFO; mặt khác, DFS được triển khai bằng danh sách LIFO.
- Trong BFS, bạn không bao giờ có thể bị mắc kẹt vào các vòng lặp hữu hạn, trong khi ở DFS, bạn có thể bị mắc kẹt vào các vòng lặp vô hạn.
BFS là gì?
BFS là một thuật toán được sử dụng để vẽ đồ thị dữ liệu hoặc tìm kiếm cây hoặc duyệt qua các cấu trúc. Thuật toán này hiệu quả truy cập và đánh dấu tất cả các nút chính trong đồ thị theo chiều rộng chính xác.
Thuật toán này chọn một nút duy nhất (điểm ban đầu hoặc điểm nguồn) trong đồ thị và sau đó truy cập tất cả các nút liền kề với nút đã chọn. Sau khi thuật toán truy cập và đánh dấu nút bắt đầu, sau đó nó di chuyển về phía các nút chưa được truy cập gần nhất và phân tích chúng.
Sau khi truy cập, tất cả các nút được đánh dấu. Việc lặp lại này tiếp tục cho đến khi tất cả các nút của biểu đồ đã được truy cập và đánh dấu thành công. Hình thức đầy đủ của BFS là tìm kiếm theo chiều rộng.
DFS là gì?
DFS là một thuật toán để tìm hoặc duyệt đồ thị hoặc cây theo hướng sâu. Việc thực thi thuật toán bắt đầu ở nút gốc và khám phá từng nhánh trước khi quay lui. Nó sử dụng cấu trúc dữ liệu ngăn xếp để ghi nhớ, lấy đỉnh tiếp theo và bắt đầu tìm kiếm, bất cứ khi nào ngõ cụt xuất hiện trong bất kỳ lần lặp nào. Dạng đầy đủ của DFS là tìm kiếm theo chiều sâu.
Sự khác biệt giữa cây nhị phân BFS và DFS
Dưới đây là những khác biệt quan trọng giữa BFS và DFS.
| BFS | DFS |
|---|---|
| BFS tìm ra con đường ngắn nhất tới đích. | DFS đi tới cuối cây con, sau đó quay lại. |
| Hình thức đầy đủ của BFS là Tìm kiếm theo chiều rộng. | Dạng đầy đủ của DFS là Tìm kiếm theo chiều sâu. |
| Nó sử dụng hàng đợi để theo dõi vị trí tiếp theo sẽ ghé thăm. | Nó sử dụng một ngăn xếp để theo dõi vị trí tiếp theo sẽ ghé thăm. |
| BFS duyệt theo cấp độ cây. | DFS duyệt theo độ sâu của cây. |
| Nó được thực hiện bằng cách sử dụng danh sách FIFO. | Nó được thực hiện bằng danh sách LIFO. |
| Nó đòi hỏi nhiều bộ nhớ hơn so với DFS. | Nó đòi hỏi ít bộ nhớ hơn so với BFS. |
| Thuật toán này đưa ra giải pháp đường đi nông nhất. | Thuật toán này không đảm bảo giải pháp đường đi nông nhất. |
| Không cần phải quay lại trong BFS. | Cần phải quay lại trong DFS. |
| Bạn không bao giờ có thể bị mắc kẹt vào các vòng lặp hữu hạn. | Bạn có thể bị mắc kẹt vào vòng lặp vô tận. |
| Nếu không tìm thấy bất kỳ mục tiêu nào, bạn có thể cần mở rộng nhiều nút trước khi tìm ra giải pháp. | Nếu bạn không tìm thấy bất kỳ mục tiêu nào, việc quay lại nút lá có thể xảy ra. |
Ví dụ về BFS
Trong ví dụ BFS sau đây, chúng ta đã sử dụng đồ thị có 6 đỉnh.
Ví dụ về BFS
Bước 1)
Bạn có một biểu đồ gồm bảy số nằm trong khoảng từ 0 – 6.
Bước 2)
0 hoặc XNUMX đã được đánh dấu là nút gốc.
Bước 3)
0 được truy cập, đánh dấu và chèn vào cấu trúc dữ liệu hàng đợi.
Bước 4)
Còn lại 0 nút liền kề và chưa được thăm dò sẽ được truy cập, đánh dấu và chèn vào hàng đợi.
Bước 5)
Việc lặp lại quá trình duyệt được lặp lại cho đến khi tất cả các nút được truy cập.
Ví dụ về DFS
Trong ví dụ sau về DFS, chúng ta đã sử dụng một đồ thị vô hướng có 5 đỉnh.
Bước 1)
Chúng tôi đã bắt đầu từ đỉnh 0. Thuật toán bắt đầu bằng cách đưa nó vào danh sách đã ghé thăm và đồng thời đưa tất cả các đỉnh liền kề của nó vào cấu trúc dữ liệu gọi là ngăn xếp.
Bước 2)
Bạn sẽ truy cập phần tử nằm ở đầu ngăn xếp, ví dụ: 1 và đi đến các nút liền kề của nó. Đó là vì 0 đã được truy cập. Vì vậy, chúng ta ghé thăm đỉnh 2.
Bước 3)
Đỉnh 2 có một đỉnh lân cận chưa được thăm trong 4. Do đó, chúng tôi thêm đỉnh đó vào ngăn xếp và thăm nó.
Bước 4)
Cuối cùng, chúng ta sẽ thăm đỉnh 3 cuối cùng, nó không có bất kỳ nút liền kề nào chưa được thăm. Chúng ta đã hoàn thành việc duyệt đồ thị bằng thuật toán DFS.
Ứng dụng của BFS
Đây là các ứng dụng của BFS:
Đồ thị không có trọng số
Thuật toán BFS có thể dễ dàng tạo đường đi ngắn nhất và cây bao trùm tối thiểu để truy cập tất cả các đỉnh của đồ thị trong thời gian ngắn nhất có thể với độ chính xác cao.
Mạng P2P
BFS có thể được triển khai để định vị tất cả các nút gần nhất hoặc lân cận trong mạng ngang hàng. Điều này sẽ tìm thấy dữ liệu cần thiết nhanh hơn.
Trình thu thập thông tin web
Công cụ tìm kiếm hoặc trình thu thập dữ liệu web có thể dễ dàng xây dựng nhiều cấp độ chỉ mục bằng cách sử dụng BFS. Việc triển khai BFS bắt đầu từ nguồn, tức là trang web, sau đó truy cập tất cả các liên kết từ nguồn đó.
Phát sóng mạng
Một gói tin được quảng bá được hướng dẫn bởi thuật toán BFS để tìm và tiếp cận tất cả các nút mà nó có địa chỉ.
Ứng dụng của DFS
Dưới đây là các ứng dụng quan trọng của DFS:
Biểu đồ có trọng số
Trong đồ thị có trọng số, việc truyền tải đồ thị DFS tạo ra cây đường đi ngắn nhất và cây bao trùm tối thiểu.
Phát hiện một chu trình trong đồ thị
Đồ thị có một chu trình nếu chúng ta tìm thấy cạnh sau trong DFS. Vì vậy, chúng ta nên chạy DFS cho biểu đồ và xác minh các cạnh sau.
Tìm đường dẫn
Chúng ta có thể chuyên môn hóa thuật toán DFS để tìm kiếm đường đi giữa hai đỉnh.
Sắp xếp theo cấu trúc liên kết
Nó chủ yếu được sử dụng để lập kế hoạch công việc từ sự phụ thuộc nhất định giữa các nhóm công việc. Trong khoa học máy tính, nó được sử dụng trong lập lịch lệnh, tuần tự hóa dữ liệu, tổng hợp logic, xác định thứ tự của các tác vụ biên dịch.
Tìm kiếm các thành phần được kết nối mạnh của một đồ thị
Nó được sử dụng trong biểu đồ DFS khi có một đường dẫn từ mỗi đỉnh trong biểu đồ đến các đỉnh còn lại khác.
Giải câu đố chỉ bằng một lời giải
Thuật toán DFS có thể dễ dàng được điều chỉnh để tìm kiếm tất cả các giải pháp cho mê cung bằng cách bao gồm các nút trên đường dẫn hiện có trong tập hợp đã truy cập.
