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

Kruskal's algorithm เป็น greedy algorithm ทำงานดังนี้:

1. สร้าง set ของ edges ทั้งหมดใน graph

2. ขณะที่ set ไม่ว่างและ vertices ยังไม่ครบ:

• ลบ minimum weight edge ออกจาก set
• เช็คว่า edge นี้สร้าง cycle หรือแค่เชื่อม 2 trees ถ้าสร้าง cycle discard edge ไม่เช่นนั้นเพิ่มเข้า tree

3. เมื่อเสร็จแล้ว จะได้ minimum spanning tree

เพื่อ implement อัลกอริทึมนี้ ต้องการ 2 data structures เพิ่ม:

แรก ต้องการ priority queue เพื่อเก็บ edges เรียงลำดับ และได้ required edge ทุก iteration

ต่อไป ต้องการ disjoint set data structure (union-find) ติดตาม elements แบ่งเป็น disjoint subsets เวลาเพิ่ม node ใหม่เช็คว่า connected แล้วหรือยัง ถ้าใช่มี cycle ถ้าไม่ union ทั้งสอง vertices

มาดู UnionFind implementation:

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

class UnionFind {
  constructor(elements) {
    this.count = elements.length;
    this.parent = {};
    elements.forEach(e => (this.parent[e] = e));
  }
  union(a, b) {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA === rootB) return;
    if (rootA < rootB) {
      if (this.parent[b] != b) this.union(this.parent[b], a);
      this.parent[b] = this.parent[a];
    } else {
      if (this.parent[a] != a) this.union(this.parent[a], b);
      this.parent[a] = this.parent[b];
    }
  }
  find(a) {
    while (this.parent[a] !== a) {
      a = this.parent[a];
    }
    return a;
  }
  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

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

ตัวอย่างการใช้งาน

let uf = new UnionFind(["A", "B", "C", "D", "E"]);
uf.union("A", "B");
uf.union("A", "C");
uf.union("C", "D");
console.log(uf.connected("B", "E"));
console.log(uf.connected("B", "D"));

ผลลัพธ์

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

false
true

มาดู Kruskal's algorithm implementation:

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

kruskalsMST() {
  const MST = new Graph();
  this.nodes.forEach(node => MST.addNode(node));
  if (this.nodes.length === 0) return MST;
  let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
  for (let node in this.edges) {
    this.edges[node].forEach(edge => {
      edgeQueue.enqueue([node, edge.node], edge.weight);
    });
  }
  let uf = new UnionFind(this.nodes);
  while (!edgeQueue.isEmpty()) {
    let nextEdge = edgeQueue.dequeue();
    let nodes = nextEdge.data;
    let weight = nextEdge.priority;
    if (!uf.connected(nodes[0], nodes[1])) {
      MST.addEdge(nodes[0], nodes[1], weight);
      uf.union(nodes[0], nodes[1]);
    }
  }
  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.addEdge("E", "G", 50);
g.kruskalsMST().display();

ผลลัพธ์

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

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