JavaScript로 이해하는 프림 알고리즘 (Prim’s Minimum Spanning Tree)

프림 알고리즘이란?

"프림 알고리즘(Prim's Algorithm)"은 "최소 신장 트리(Minimum Spanning Tree)"를 찾기 위한 대표적인 방법 중 하나입니다. 이 알고리즘은 하나의 정점에서 시작해, "가장 가까운 정점"을 차례로 선택하며 트리를 확장해나가는 방식으로 동작합니다. 크루스칼 알고리즘이 "간선 중심(edge-based)"이라면, 프림은 "정점 중심(vertex-based)"이라는 점에서 구별됩니다.

---

작동 방식 요약

프림 알고리즘은 다음과 같은 단계로 작동합니다:

1. 임의의 시작 정점을 선택합니다.
2. 해당 정점과 인접한 간선 중에서 가장 가중치가 작은 간선을 선택합니다.
3. 선택된 간선으로 연결된 정점을 방문하며 트리에 포함시킵니다.
4. 방문하지 않은 정점들 중에서 트리에 연결할 수 있는 최소 비용의 간선을 반복해서 선택합니다.
5. 모든 정점을 방문할 때까지 위 과정을 반복합니다.

"우선순위 큐"(보통 Min Heap)를 활용하면 각 단계에서 가장 가중치가 낮은 간선을 빠르게 선택할 수 있습니다.

01234567891011

---

JavaScript 구현 예제

그래프 인접 리스트 구조 설명

그래프는 인접 리스트로 표현됩니다. 각 정점은 인접한 정점과 간선 가중치를 갖는 배열을 가지며, 전체 그래프는 객체 또는 배열로 구성됩니다.

// 예시 그래프 (인접 리스트 형태)
// 정점: 0, 1, 2, 3
// 각 요소는 [연결된 정점, 가중치]를 나타냄
const graph = {
  0: [[1, 2], [3, 6]],
  1: [[0, 2], [2, 3], [3, 8]],
  2: [[1, 3], [3, 7]],
  3: [[0, 6], [1, 8], [2, 7]]
};

프림 알고리즘 구현 코드

function prim(graph) {
  const visited = new Set(); // 방문한 정점 추적
  const heap = [[0, 0]]; // [가중치, 정점] 형태의 최소 힙 (시작 정점 0에서 시작)
  let totalCost = 0;

  while (heap.length > 0) {
    // 가중치가 가장 작은 간선 선택
    heap.sort((a, b) => a[0] - b[0]); // 간단한 정렬로 min heap 대체
    const [weight, u] = heap.shift();

    if (visited.has(u)) continue; // 이미 방문한 정점이면 skip

    visited.add(u);
    totalCost += weight;

    for (let [v, w] of graph[u]) {
      if (!visited.has(v)) {
        heap.push([w, v]); // 인접한 정점을 우선순위 큐에 추가
      }
    }
  }

  return totalCost;
}

// 실행 예시
console.log("Total Cost (Prim):", prim(graph));

코드 설명

• visited: 이미 트리에 포함된 정점을 추적합니다.
• heap: 다음에 확장할 정점을 선택하기 위한 우선순위 큐 역할을 합니다.
• totalCost: 현재까지 선택된 간선들의 가중치 합입니다.

---

시간 복잡도 및 크루스칼과의 비교

• 시간 복잡도: O(E log V) (우선순위 큐를 제대로 구현했을 경우)
• 공간 복잡도: O(V + E) (인접 리스트 기반)

항목	프림 알고리즘	크루스칼 알고리즘
중심 개념	"정점 중심" (Vertex-based)	"간선 중심" (Edge-based)
자료구조 활용	"우선순위 큐"	"Union-Find"
희소 그래프 효율성	보통	더 효율적일 수 있음

---

활용 사례

• 통신망 구축: 노드 간 최단 경로를 기반으로 네트워크 선 연결
• 지도 및 내비게이션 시스템: 최소 거리 기반 경로 구성
• 센서 네트워크 구성: 거리와 전력 효율을 고려한 연결 구조

---

마무리 및 CTA

"프림 알고리즘"은 그래프에서 최소 비용으로 정점을 연결하는 가장 효율적인 방법 중 하나로, 특히 "우선순위 큐"를 활용한 정점 확장 방식이 핵심입니다.

더 많은 그래프 알고리즘을 학습하고 싶다면 아래 자료를 참고해보시기 바랍니다:

추천 자료:

• Visualgo - MST 시각화
• Programiz - Prim's Algorithm
• GeeksforGeeks - Prim's MST