BFS là gì?
BFS là một thuật toán được sử dụng để vẽ biểu đồ dữ liệu hoặc cây tìm kiếm hoặc các cấu trúc chuyển ngang. Thuật toán truy cập và đánh dấu hiệu quả tất cả các nút chính trong biểu đồ 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 lân cận với nút đã chọn. Khi thuật toán truy cập và đánh dấu nút bắt đầu, sau đó nó sẽ di chuyển đến các nút không đượ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 đều được đánh dấu. Các bước lặp 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. Dạng đầy đủ của BFS là tìm kiếm theo chiều rộng.
Trong BSF này Vs. Hướng dẫn cây nhị phân DFS, bạn sẽ học:
- BFS là gì?
- DFS là gì?
- Ví dụ về BFS
- Ví dụ về DFS
- Sự khác biệt giữa BFS và DFS Binary Tree
- Các ứng dụng của BFS
- Các ứng dụng của DFS
DFS là gì?
DFS là một thuật toán để tìm hoặc duyệt qua đồ thị hoặc cây theo hướng phân khu 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 bẻ khóa ngược. 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 một điểm cuối 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 độ sâu trước tiên.
Ví dụ về BFS
Trong ví dụ sau về DFS, 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ố khác nhau, từ 0 - 6.
Bước 2)
0 hoặc 0 đã đượ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à không được truy cập sẽ được truy cập, đánh dấu và chèn vào hàng đợi.
Bước 5)
Các phép lặp đi ngang đượ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 ta đã bắt đầu từ đỉnh 0. Thuật toán bắt đầu bằng cách đưa nó vào danh sách đã 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 được gọi là ngăn xếp.
Bước 2)
Bạn sẽ truy cập vào phần tử, ví dụ, ở trên cùng của ngăn xếp, 1 và đi đến các nút liền kề của nó. Đó là bởi vì số 0 đã được truy cập. Do đó, chúng ta truy cập đỉnh 2.
Bước 3)
Đỉnh 2 có một đỉnh gần đó chưa được duyệt 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ẽ đến thăm đỉnh cuối cùng 3, nó không có bất kỳ nút liền kề nào chưa được duyệt. Chúng tôi đã hoàn thành việc duyệt đồ thị bằng thuật toán DFS.
Sự khác biệt giữa BFS và DFS Binary Tree
| BFS | DFS |
| BFS tìm đường đi ngắn nhất đến đích. | DFS đi đến cuối cây con, sau đó là dấu lùi. |
| Dạng đầy đủ của BFS là Breadth-First Search. | Dạng đầy đủ của DFS là Tìm kiếm đầu tiên theo chiều sâu. |
| Nó sử dụng một hàng đợi để theo dõi vị trí tiếp theo sẽ đến thăm. | Nó sử dụng một ngăn xếp để theo dõi vị trí tiếp theo sẽ đến thăm. |
| BFS truyền theo cấp độ cây. | DFS truyền 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 cách sử dụng danh sách LIFO. |
| Nó yêu cầu nhiều bộ nhớ hơn so với DFS. | Nó yêu cầu ít bộ nhớ hơn so với BFS. |
| Thuật toán này đưa ra giải pháp đường dẫn nông nhất. | Thuật toán này không đảm bảo giải pháp đường dẫn nông nhất. |
| Không cần bẻ khóa ngược trong BFS. | Cần có backtracking trong DFS. |
| Bạn không bao giờ có thể bị mắc kẹt vào những vòng lặp hữu hạn. | Bạn có thể bị mắc kẹt vào những vòng lặp vô hạn. |
| Nếu bạn không tìm thấy bất kỳ mục tiêu nào, bạn có thể cần phải mở rộng nhiều nút trước khi giải pháp được tìm thấy. | Nếu bạn không tìm thấy bất kỳ mục tiêu nào, việc bẻ khóa ngược nút lá có thể xảy ra. |
Các ứng dụng của BFS
Đây là các ứng dụng của BFS:
Đồ thị không trọng số:
Thuật toán BFS có thể dễ dàng tạo ra một đường đi ngắn nhất và một cây bao trùm tối thiểu để thăm 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 thực hiện để đị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ác công cụ tìm kiếm hoặc trình thu thập thông tin 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, là trang web, sau đó nó 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 được quảng bá được hướng dẫn bởi thuật toán BFS để tìm và đến tất cả các nút mà nó có địa chỉ.
Các ứng dụng của DFS
Dưới đây là các ứng dụng quan trọng của DFS:
Đồ thị có trọng số:
Trong một đồ thị có trọng số, việc duyệt đồ 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 kỳ trong một đồ thị:
Một đồ thị có một chu kỳ nếu chúng ta tìm thấy một cạnh sau trong DFS. Do đó, chúng ta nên chạy DFS cho đồ thị và xác minh các cạnh phía sau.
Tìm đường dẫn:
Chúng ta có thể chuyên về thuật toán DFS để tìm kiếm một đườ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 lịch công việc từ các phụ thuộc đã cho trong nhóm công việc. Trong khoa học máy tính, nó được sử dụng trong việc lập lịch hướng dẫn, tuần tự hóa dữ liệu, tổng hợp logic, xác định thứ tự của các nhiệm vụ biên dịch.
Tìm kiếm các thành phần được kết nối mạnh mẽ của một biểu đồ:
Nó được sử dụng trong đồ thị DFS khi có một đường đi từ mỗi và mọi đỉnh trong đồ thị đến các đỉnh còn lại khác.
Giải các câu đố chỉ với một giải pháp:
Thuật toán DFS có thể dễ dàng điều chỉnh để tìm kiếm tất cả các giải pháp cho một mê cung bằng cách bao gồm các nút trên đường hiện có trong tập hợp đã thăm.
NHỮNG KHÁC BIỆT CHÍNH:
- BFS tìm đường đi ngắn nhất đến đích trong khi DFS đi đến cuối cây con, sau đó chuyển ngược lại.
- Dạng đầy đủ của BFS là Breadth-First Search trong khi dạng đầy đủ của DFS là Depth First Search.
- BFS sử dụng một hàng đợi để theo dõi vị trí tiếp theo sẽ đến thăm. trong khi DFS sử dụng một ngăn xếp để theo dõi vị trí tiếp theo để truy cập.
- BFS truyền theo cấp độ cây trong khi DFS truyền theo độ sâu của cây.
- BFS được thực hiện bằng cách sử dụng danh sách FIFO trong khi DFS được thực hiện bằng cách sử dụng danh sách LIFO.
- Trong BFS, bạn không bao giờ có thể bị mắc kẹt trong các vòng lặp hữu hạn trong khi trong DFS, bạn có thể bị mắc kẹt vào các vòng lặp vô hạn.