Duyệt tìm kiếm theo chiều rộng (BFS) trong JavaScript

BFS ghé thăm các đỉnh lân cận trước đỉnh con, và dùng queue trong quá trình tìm kiếm. Cách BFS hoạt động:

• Ghé thăm đỉnh kề chưa thăm. Đánh dấu đã thăm. Hiển thị nó. Thêm vào queue.
• Nếu không tìm thấy đỉnh kề, lấy đỉnh đầu tiên ra khỏi queue.
• Lặp lại Quy tắc 1 và 2 cho đến khi queue rỗng.

Hãy xem minh họa cách BFS Traversal hoạt động:

Bước	Duyệt	Mô tả
1		Khởi tạo queue.
2		Bắt đầu bằng cách ghé thăm S (nút bắt đầu) và đánh dấu đã thăm.
3		Xem nút kề chưa thăm từ S. Ví dụ này có 3 nút nhưng theo bảng chữ cái chọn A, đánh dấu đã thăm và thêm vào queue.
4		Tiếp theo, nút kề chưa thăm từ S là B. Đánh dấu đã thăm và thêm vào queue.
5		Tiếp theo, nút kề chưa thăm từ S là C. Đánh dấu đã thăm và thêm vào queue.
6		Bây giờ, S không còn nút kề chưa thăm. Vậy lấy ra khỏi queue và tìm A.
7		Từ A có D là nút kề chưa thăm. Đánh dấu đã thăm và thêm vào queue.

Ở giai đoạn này, không còn nút chưa đánh dấu (chưa thăm). Nhưng theo thuật toán ta tiếp tục lấy ra khỏi queue để lấy tất cả nút chưa thăm. Khi queue rỗng, chương trình kết thúc.

Hãy xem cách triển khai trong JavaScript.

Ví dụ

BFS(node) {
  // Tạo Queue và thêm nút khởi tạo vào
  let q = new Queue(this.nodes.length);
  let explored = new Set();
  q.enqueue(node);
  // Đánh dấu nút đầu tiên đã khám phá
  explored.add(node);
  // Tiếp tục cho đến khi queue rỗng
  while (!q.isEmpty()) {
    let t = q.dequeue();
    // Log mọi phần tử ra khỏi Queue
    console.log(t);
    // 1. Trong object edges, tìm nút mà nút này kết nối trực tiếp.
    // 2. Lọc bỏ nút đã được khám phá.
    // 3. Đánh dấu mỗi nút chưa khám phá là đã khám phá và thêm vào queue.
    this.edges[t]
      .filter(n => !explored.has(n))
      .forEach(n => {
        explored.add(n);
        q.enqueue(n);
      });
  }
}

Bạn có thể kiểm tra hàm này bằng cách sau:

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");

Kết quả

Điều này sẽ cho ra kết quả:

A C B D G E F