Javascript의 Kruskal 알고리즘

Kruskal의 알고리즘은 다음과 같이 작동하는 욕심 많은 알고리즘입니다 -

1. 그래프의 모든 간선 세트를 생성합니다.

2. 위의 집합이 비어 있지 않고 모든 정점이 포함되는 것은 아니지만

• 이 세트에서 최소 가중치 가장자리를 제거합니다.
• 이 에지가 순환을 형성하는지 아니면 2개의 나무를 연결하는지 확인합니다. 순환을 형성하면 이 모서리를 버리고, 그렇지 않으면 트리에 추가합니다.

3. 위의 처리가 완료되면 최소 스패닝 트리가 생깁니다.

이 알고리즘을 구현하려면 2개의 데이터 구조가 더 필요합니다.

먼저 가장자리를 정렬된 순서로 유지하고 각 반복에서 필요한 가장자리를 얻는 데 사용할 수 있는 우선 순위 대기열이 필요합니다.

다음으로, 분리된 집합 데이터 구조가 필요합니다. disjoint-set 데이터 구조(union-find 데이터 구조 또는 merge-find set이라고도 함)는 여러 개의 disjoint(비중첩) 하위 집합으로 분할된 요소 집합을 추적하는 데이터 구조입니다. 트리에 새 노드를 추가할 때마다 이미 연결되어 있는지 확인합니다. 그렇다면 주기가 있습니다. 그렇지 않은 경우 가장자리의 두 정점을 합집합합니다. 그러면 동일한 하위 집합에 추가됩니다.

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