Prim의 알고리즘은 가중된 무방향 그래프에 대한 최소 스패닝 트리를 찾는 욕심 많은 알고리즘입니다. 모든 정점을 포함하는 트리를 형성하는 가장자리의 하위 집합을 찾습니다. 여기서 트리의 모든 가장자리의 총 가중치는 최소화됩니다.
이 알고리즘은 각 단계에서 임의의 시작 정점에서 한 번에 하나의 정점을 트리에서 다른 정점으로 가장 저렴한 연결을 추가하여 이 트리를 구축하는 방식으로 작동합니다.
Prim의 알고리즘은 어떻게 작동합니까?
Prim의 알고리즘이 작동하는 방식에 대한 그림을 살펴보겠습니다. -
1. 임의의 노드를 루트 노드로 선택합니다. 이 경우 S 노드를 Prim의 스패닝 트리의 루트 노드로 선택합니다. 이 노드는 임의로 선택되므로 모든 노드가 루트 노드가 될 수 있습니다. 모든 비디오가 루트 노드가 될 수 있는 이유가 궁금할 수 있습니다. 따라서 답은 스패닝 트리에 그래프의 모든 노드가 포함되어 있고 연결되어 있기 때문에 트리의 나머지 부분에 연결하는 가장자리가 최소한 하나는 있어야 한다는 것입니다.
2. 나가는 간선을 확인하고 비용이 덜 드는 간선을 선택합니다. 루트 노드 S를 선택한 후 S, A, S, C가 각각 가중치가 7과 8인 두 개의 간선임을 알 수 있습니다. 우리는 가장자리 S, A가 다른 것보다 작기 때문에 선택합니다.
이제 트리 S-7-A는 하나의 노드로 취급되며 여기서 나가는 모든 가장자리를 확인합니다. 비용이 가장 저렴한 것을 선택하여 트리에 포함시킵니다.
이 단계 후에 S-7-A-3-C 트리가 형성됩니다. 이제 다시 노드로 처리하고 모든 가장자리를 다시 확인합니다. 그러나 우리는 가장 비용이 적게 드는 가장자리만 선택할 것입니다. 이 경우 C-3-D는 다른 가장자리의 비용 8, 6, 4 등보다 적은 새 가장자리입니다.
노드 D를 추가한 후 스패닝 트리에 대해 이제 동일한 비용을 갖는 두 개의 모서리, 즉 D-2-T 및 D-2-B가 있습니다. 따라서 둘 중 하나를 추가할 수 있습니다. 그러나 다음 단계는 다시 가장자리 2를 최소 비용으로 산출합니다. 따라서 우리는 양쪽 가장자리가 포함된 스패닝 트리를 보여주고 있습니다.
이제 코드에서 동일하게 구현하는 방법을 살펴보겠습니다.
예시
primsMST() {
// Initialize graph that'll contain the MST
const MST = new Graph();
if (this.nodes.length === 0) {
return MST;
}
// Select first node as starting node
let s = this.nodes[0];
// Create a Priority Queue and explored set
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
let explored = new Set();
explored.add(s);
MST.addNode(s);
// Add all edges from this starting node to the PQ taking weights as priority
this.edges[s].forEach(edge => {
edgeQueue.enqueue([s, edge.node], edge.weight);
});
// Take the smallest edge and add that to the new graph
let currentMinEdge = edgeQueue.dequeue();
while (!edgeQueue.isEmpty()) {
// COntinue removing edges till we get an edge with an unexplored node
while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
currentMinEdge = edgeQueue.dequeue();
}
let nextNode = currentMinEdge.data[1];
// Check again as queue might get empty without giving back unexplored element
if (!explored.has(nextNode)) {
MST.addNode(nextNode);
MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
// Again add all edges to the PQ
this.edges[nextNode].forEach(edge => {
edgeQueue.enqueue([nextNode, edge.node], edge.weight);
});
// Mark this node as explored 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
초기 그래프는 -
예시
/** * A * / | \ * C | B * \ | | * D G * | / * E * | * F */
출력
현재 그래프는 다음과 같습니다. -
/** * A * |\ * C | B * \ | | * D G * | * E * | * F * */
가장 값비싼 모서리를 제거하고 이제 스패닝 트리를 갖게 되었습니다.