Thuật toán Prim trong JavaScript

Thuật toán Prim là thuật toán tham lam tìm minimum spanning tree cho đồ thị vô hướng có trọng số. Nó tìm tập con cạnh tạo thành cây bao gồm mọi đỉnh, nơi tổng trọng số tất cả cạnh trong cây được tối thiểu hóa.

Thuật toán hoạt động bằng cách xây dựng cây này từng đỉnh một, từ một đỉnh bắt đầu tùy ý, ở mỗi bước thêm kết nối rẻ nhất có thể từ cây đến đỉnh khác.

Cách thuật toán Prim hoạt động?

Hãy xem minh họa cách thuật toán Prim hoạt động:

1. Chọn một nút tùy ý làm nút gốc: Trong trường hợp này, ta chọn nút S làm gốc của cây khung Prim. Nút này chọn tùy ý, nên bất kỳ nút nào cũng có thể là gốc. Có thể thắc mắc tại sao bất kỳ nút nào cũng có thể là gốc. Câu trả lời: trong cây khung tất cả nút của đồ thị được bao gồm và vì nó liên thông thì phải có ít nhất một cạnh nối nó với phần còn lại của cây.

2. Kiểm tra các cạnh ra và chọn cái chi phí nhỏ hơn: Sau khi chọn gốc S, ta thấy S-A và S-C là hai cạnh với trọng số 7 và 8. Ta chọn cạnh S-A vì nhỏ hơn.

Bây giờ, cây S-7-A được xem như một nút và ta kiểm tra tất cả cạnh ra từ nó. Chọn cạnh chi phí thấp nhất và đưa vào cây.

Sau bước này, cây S-7-A-3-C được hình thành. Ta lại xem nó như một nút và kiểm tra tất cả cạnh lại. Tuy nhiên, chỉ chọn cạnh chi phí nhỏ nhất. Trong trường hợp này, C-3-D là cạnh mới nhỏ hơn các cạnh khác chi phí 8, 6, 4, v.v.

Sau khi thêm nút D vào cây khung, ta có hai cạnh ra từ nó cùng chi phí, tức D-2-T và D-2-B. Vậy ta có thể thêm cái nào cũng được. Nhưng bước tiếp theo sẽ lại cho cạnh 2 là chi phí nhỏ nhất. Do đó, ta đang thể hiện cây khung với cả hai cạnh.

Bây giờ hãy xem cách triển khai trong code:

Ví dụ

primsMST() {
  // Khởi tạo graph chứa MST
  const MST = new Graph();
  if (this.nodes.length === 0) {
    return MST;
  }
  // Chọn nút đầu tiên làm nút bắt đầu
  let s = this.nodes[0];
  // Tạo Priority Queue và tập explored
  let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
  let explored = new Set();
  explored.add(s);
  MST.addNode(s);
  // Thêm tất cả cạnh từ nút bắt đầu vào PQ lấy trọng số làm priority
  this.edges[s].forEach(edge => {
    edgeQueue.enqueue([s, edge.node], edge.weight);
  });
  // Lấy cạnh nhỏ nhất và thêm vào graph mới
  let currentMinEdge = edgeQueue.dequeue();
  while (!edgeQueue.isEmpty()) {
    // Tiếp tục lấy cạnh cho đến khi có cạnh với nút chưa khám phá
    while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
      currentMinEdge = edgeQueue.dequeue();
    }
    let nextNode = currentMinEdge.data[1];
    // Kiểm tra lại vì queue có thể rỗng mà không trả về phần tử chưa khám phá
    if (!explored.has(nextNode)) {
      MST.addNode(nextNode);
      MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
      // Lại thêm tất cả cạnh vào PQ
      this.edges[nextNode].forEach(edge => {
        edgeQueue.enqueue([nextNode, edge.node], edge.weight);
      });
      // Đánh dấu nút này đã khám phá
      explored.add(nextNode);
      s = nextNode;
    }
  }
  return MST;
}

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

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", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("C", "D", 3);
g.addEdge("D", "E", 8);
g.addEdge("E", "F", 10);
g.addEdge("B", "G", 9);
g.primsMST().display();

Kết quả

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

A->B, D
B->A, G
D->A, C, E
C->D
E->D, F
G->B
F->E

Lưu ý đồ thị ban đầu là:

Ví dụ

/**
 *       A
 *     / | \
 *    C  |  B
 *     \ |  |
 *      D  G
 *      | /
 *      E
 *      |
 *      F */

Kết quả

Đồ thị hiện tại trông như:

/**
 *       A
 *        |\
 *      C  | B
 *       \ | |
 *        D  G
 *        |
 *        E
 *        |
 *        F 
 *        * */

Chúng ta đã loại bỏ các cạnh tốn kém nhất và giờ có một cây khung.