อัลกอริทึม Prim ใน JavaScript

Prim's algorithm เป็น greedy algorithm หา minimum spanning tree สำหรับ weighted undirected graph หา subset ของ edges ที่สร้าง tree รวมทุก vertex โดย total weight น้อยที่สุด

อัลกอริทึมสร้าง tree ทีละ vertex จาก arbitrary starting vertex แต่ละขั้นเพิ่ม cheapest connection จาก tree ไป vertex อื่น

Prim's algorithm ทำงานอย่างไร?

มาดูภาพประกอบ:

1. เลือก arbitrary node เป็น root node: กรณีนี้เลือก S เป็น root ของ Prim's spanning tree Node ใดก็ได้เพราะ spanning tree รวมทุก nodes และ connected จึงมีอย่างน้อย 1 edge เชื่อมไปยังส่วนที่เหลือ

2. เช็ค outgoing edges เลือกที่ cost น้อยกว่า: หลังเลือก S ดู S-A และ S-C weights 7 และ 8 เลือก S-A เพราะน้อยกว่า

ตอนนี้ tree S-7-A ถูกถือเป็น node เดียว เช็ค edges ออกจากมัน เลือก lowest cost รวมเข้า tree

หลังขั้นนี้ได้ tree S-7-A-3-C ต่อไปเช็ค edges อีกครั้ง เลือก least cost edge C-3-D น้อยกว่า edges อื่นๆ 8, 6, 4 ฯลฯ

หลังเพิ่ม node D มี 2 edges ออกไป cost เท่ากัน D-2-T และ D-2-B เพิ่มได้อันไหนก็ได้ แต่ขั้นต่อไปก็ได้ edge 2 อีก แสดง spanning tree ทั้งสอง edges

มาดูการนำไปใช้ในโค้ด:

ตัวอย่างโค้ด

primsMST() {
  const MST = new Graph();
  if (this.nodes.length === 0) return MST;
  let s = this.nodes[0];
  let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
  let explored = new Set();
  explored.add(s);
  MST.addNode(s);
  this.edges[s].forEach(edge => {
    edgeQueue.enqueue([s, edge.node], edge.weight);
  });
  let currentMinEdge = edgeQueue.dequeue();
  while (!edgeQueue.isEmpty()) {
    while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
      currentMinEdge = edgeQueue.dequeue();
    }
    let nextNode = currentMinEdge.data[1];
    if (!explored.has(nextNode)) {
      MST.addNode(nextNode);
      MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
      this.edges[nextNode].forEach(edge => {
        edgeQueue.enqueue([nextNode, edge.node], edge.weight);
      });
      explored.add(nextNode);
      s = nextNode;
    }
  }
  return MST;
}

ทดสอบได้ดังนี้:

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

ผลลัพธ์

จะได้ผลลัพธ์ดังนี้:

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

Initial graph คือ:

ตัวอย่าง

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

ผลลัพธ์

Graph ปัจจุบันเป็น:

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

เราลบ costly edges ออก และได้ spanning tree