BFS thăm các đỉnh lân cận trước khi thăm các đỉnh con và một hàng đợi được sử dụng trong quá trình tìm kiếm. Sau đây là cách BFS hoạt động -
- Ghé thăm đỉnh không được chờ đợi liền kề. Đánh dấu nó là đã ghé thăm. Hiển thị nó. Chèn nó vào hàng đợi.
- Nếu không tìm thấy đỉnh liền kề, hãy xóa đỉnh đầu tiên khỏi hàng đợi.
- Lặp lại Quy tắc 1 và Quy tắc 2 cho đến khi hàng đợi trống.
Hãy cùng chúng tôi xem minh họa về cách hoạt động của BFS Traversal:
| Bước | Truyền tải | Mô tả |
|---|---|---|
| 1 |  | Khởi tạo hàng đợi. |
| 2 |  | Chúng tôi bắt đầu bằng cách truy cập S (nút bắt đầu) và đánh dấu nó là đã truy cập. |
| 3 |  | Sau đó, chúng tôi nhìn thấy một nút liền kề không được sử dụng từ S. Trong ví dụ này, chúng tôi có ba nút nhưng theo thứ tự bảng chữ cái, chúng tôi chọn A, đánh dấu nó là đã ghé thăm và xếp hàng. |
| 4 |  | Tiếp theo, nút liền kề không được sử dụng từ S là B . Chúng tôi đánh dấu nó là đã ghé thăm và xếp hàng. |
| 5 |  | Tiếp theo, nút liền kề không được sử dụng từ S là C . Chúng tôi đánh dấu nó là đã ghé thăm và xếp hàng. |
| 6 |  | Bây giờ, S không có nút liền kề không được kiểm soát. Vì vậy, chúng tôi xếp hàng và tìm thấy A . |
| 7 | | Từ A chúng tôi có D như một nút liền kề không được sử dụng. Chúng tôi đánh dấu nó là đã ghé thăm và xếp hàng. |
Ở giai đoạn này, chúng ta không có nút nào chưa được đánh dấu (không được đánh dấu). Nhưng theo thuật toán, chúng tôi tiếp tục giảm giá trị để có được tất cả các nút chưa được sử dụng. Khi hàng đợi trống, chương trình kết thúc.
Hãy xem cách chúng ta có thể triển khai điều này trong JavaScript.
Ví dụ
BFS(node) {
// Create a Queue and add our initial node in it
let q = new Queue(this.nodes.length);
let explored = new Set();
q.enqueue(node);
// Mark the first node as explored explored.
add(node);
// We'll continue till our queue gets empty
while (!q.isEmpty()) {
let t = q.dequeue();
// Log every element that comes out of the Queue
console.log(t);
// 1. In the edges object, we search for nodes this node is directly connected to.
// 2. We filter out the nodes that have already been explored.
// 3. Then we mark each unexplored node as explored and add it to the queue.
this.edges[t]
.filter(n => !explored.has(n))
.forEach(n => {
explored.add(n);
q.enqueue(n);
});
}
} Bạn có thể kiểm tra chức năng này bằng cách sử dụng -
Ví dụ
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");
g.BFS("A"); Đầu ra
Điều này sẽ cung cấp đầu ra -
A C B D G E F