อัลกอริทึมของ Kruskal ใน Javascript

อัลกอริธึมของ Kruskal เป็นอัลกอริธึมที่โลภที่ทำงานดังนี้ -

1. สร้างชุดของขอบทั้งหมดในกราฟ

2. ในขณะที่ชุดด้านบนไม่ว่างเปล่าและไม่ครอบคลุมจุดยอดทั้งหมด

• เอาขอบน้ำหนักขั้นต่ำออกจากชุดนี้
• ตรวจสอบขอบนี้ว่ากำลังก่อตัวเป็นวงจรหรือเพียงแค่เชื่อมต้นไม้ 2 ต้นเข้าด้วยกัน ถ้ามันก่อตัวเป็นวัฏจักร เราจะละทิ้งขอบนี้ มิฉะนั้น เราจะเพิ่มมันเข้าไปในต้นไม้ของเรา

3. เมื่อการประมวลผลข้างต้นเสร็จสมบูรณ์ เรามีแผนผังที่ขยายขั้นต่ำ

ในการใช้อัลกอริทึมนี้ เราจำเป็นต้องมีโครงสร้างข้อมูลเพิ่มอีก 2 โครงสร้าง

อันดับแรก เราต้องการลำดับความสำคัญที่เราสามารถใช้เพื่อให้ขอบอยู่ในลำดับที่จัดเรียง และรับขอบที่จำเป็นของเราในการทำซ้ำแต่ละครั้ง

ต่อไป เราต้องการโครงสร้างข้อมูลชุดที่ไม่ปะติดปะต่อกัน โครงสร้างข้อมูลชุดที่ไม่ปะติดปะต่อกัน (เรียกอีกอย่างว่าโครงสร้างข้อมูล union-find หรือชุด merge-find) เป็นโครงสร้างข้อมูลที่ติดตามชุดขององค์ประกอบที่แบ่งเป็นชุดย่อยที่ไม่ต่อเนื่องกัน (ไม่ทับซ้อนกัน) จำนวนหนึ่ง เมื่อใดก็ตามที่เราเพิ่มโหนดใหม่ให้กับต้นไม้ เราจะตรวจสอบว่ามีการเชื่อมต่อแล้วหรือไม่ ถ้าใช่ เราก็มีวัฏจักร ถ้าไม่ เราจะทำการรวมจุดยอดทั้งสองของขอบ สิ่งนี้จะเพิ่มลงในเซตย่อยเดียวกัน

ให้เราดูการใช้งานโครงสร้างข้อมูล UnionFind หรือ DisjointSet &minsu;

ตัวอย่าง

class UnionFind {
   constructor(elements) {
      // Number of disconnected components
      this.count = elements.length;

      // Keep Track of connected components
      this.parent = {};

      // Initialize the data structure such that all
      // elements have themselves as parents
      elements.forEach(e => (this.parent[e] = e));
   }

   union(a, b) {
      let rootA = this.find(a);
      let rootB = this.find(b);

      // Roots are same so these are already connected.
      if (rootA === rootB) return;

      // Always make the element with smaller root the parent.
      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];
      }
   }

   // Returns final parent of a node
   find(a) {
      while (this.parent[a] !== a) {
         a = this.parent[a];
      }
      return a;
   }

   // Checks connectivity of the 2 nodes
   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 โดยใช้โครงสร้างข้อมูลนี้ -

ตัวอย่าง

kruskalsMST() {
   // Initialize graph that'll contain the MST
   const MST = new Graph();
   this.nodes.forEach(node => MST.addNode(node));
   if (this.nodes.length === 0) {
      return MST;
   }

   // Create a Priority Queue
   edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);

   // Add all edges to the Queue:
   for (let node in this.edges) {
      this.edges[node].forEach(edge => {
         edgeQueue.enqueue([node, edge.node], edge.weight);
      });
   }

   let uf = new UnionFind(this.nodes);

   // Loop until either we explore all nodes or queue is empty
   while (!edgeQueue.isEmpty()) {
      // Get the edge data using destructuring
      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