프림 알고리즘: 최소 신장 트리와 연결되지 않은 그래프 처리

프림은 이미 연결한 정점 집합에서 바깥으로 나가는 가장 싼 간선을 반복해서 고릅니다. 모든 정점이 연결되어 있으면 최소 신장 트리이며, 연결되지 않았다면 각 연결 요소의 최소 신장 트리를 모은 숲이 됩니다.

선수 지식: 무방향 가중 그래프·visited·최솟값 순회

• key가 누적 최단 거리가 아님을 설명하기
• 선택 간선과 총 가중치를 추적하기
• connected·components로 연결 실패를 구분하기

한 출발점의 거리가 아니라 전체 연결 비용을 줄입니다

무방향 가중 그래프의 신장 트리는 모든 정점을 연결하면서 순환이 없는 간선 집합입니다. 연결된 정점 V개에는 V−1개의 선택 간선이 필요합니다. 최소 신장 트리는 그런 집합 중 가중치 합이 최소인 것입니다. 출발점에서 각 정점으로 가는 거리를 최소화하는 문제와 다르므로, 최소 신장 트리 안의 경로가 원래 그래프의 최단 경로일 필요는 없습니다.

예제는 간선 한 개를 [u,v,w]로 받으며 내부에서 양방향 인접 목록을 만듭니다. 입력에 같은 무방향 간선을 두 번 적을 필요는 없습니다. 서로 같은 두 정점 사이의 평행 간선도 각각 유지하여 더 싼 연결을 선택할 수 있습니다. 자기 루프는 다른 정점을 연결하지 않으므로 선택되지 않습니다. 가중치는 음수도 허용하지만 안전한 정수로 한정하며, 전체 간선 가중치 절댓값 합도 안전한 정수 범위인지 검사합니다.

key는 현재 집합에 붙일 수 있는 최소 간선입니다

각 미방문 정점 v의 key[v]에는 지금까지 선택한 집합과 v 사이에서 찾은 최소 간선 가중치를 저장합니다. 그 간선의 반대편 정점은 parent[v]에 둡니다. 시작 정점의 key를 0으로 두고, 미방문 정점 중 유한한 key가 가장 작은 것을 선택합니다. 새 정점 u를 넣으면 u의 이웃에 대해 key[v]와 간선 가중치 w를 직접 비교합니다. key[u]+w를 비교하면 최단 경로의 누적 거리를 구하는 다른 갱신이 됩니다.

후보 key는 더 싼 연결을 발견하면 줄어듭니다. 한 번 선택한 정점에 대해서는 부모를 다시 바꾸지 않으므로 선택 간선들은 현재 집합에 정점을 하나씩 추가하며 순환 없이 이어집니다.

경계를 가로지르는 최소 간선은 안전하게 고를 수 있습니다

현재 선택 집합 S와 바깥 정점 집합을 나누면 둘 사이의 간선들이 하나의 경계를 가로지릅니다. 프림이 고르는 것은 이 간선 중 최소 가중치입니다. 현재 선택 간선들을 포함하는 최소 신장 트리에서 그 간선이 빠져 있다고 생각해 보세요. 그 간선을 추가하면 생기는 순환에는 같은 경계를 가로지르는 다른 간선이 있습니다. 그 다른 간선을 빼면 연결은 유지되고, 선택한 간선이 최소이므로 총비용은 증가하지 않습니다.

따라서 이번 간선을 포함하도록 바꾸어도 최소인 트리가 있으며, 이 논리를 반복하여 선택의 정당성을 이어갈 수 있습니다. 가중치가 같은 간선이 여럿이면 최소 신장 트리도 여럿일 수 있습니다. 특정 간선 목록 하나가 유일한 정답이라고 가정하지 말고, 전체 연결·순환 없음·간선 수·가중치 합을 함께 보세요. 가중치가 음수여도 위 교환 논리는 유지되므로, 음수 때문에 프림을 거절할 필요는 없습니다.

남은 key가 무한대이면 새 연결 요소를 시작합니다

미방문 정점이 남았는데 유한한 key를 가진 정점이 없다면 현재 집합에서 더 갈 수 있는 곳이 없습니다. 없는 간선을 비용 무한대로 선택한 것처럼 처리해서는 안 됩니다. 이 구현은 그 탐색을 끝내고 다음 미방문 정점을 새 시작점으로 잡습니다. 반환값의 components는 이렇게 시작한 연결 요소 수이고, connected는 빈 그래프 또는 연결 요소 한 개일 때 참입니다. 빈 그래프는 components=0, 총합=0인 자명한 경우로 약속합니다.

예를 들어 간선 0—1:2와 2—3:3만 있으면 components=2, connected=false, 총합=5입니다. 이 값은 모든 정점이 하나로 연결된 트리의 비용이 아니라 각 요소를 최소로 연결한 숲의 비용입니다. 정점마다 최소 후보를 선형 탐색하므로 시간은 O(V²+E), 인접 목록과 상태 공간은 O(V+E)입니다. 우선순위 큐를 사용하는 변형과 복잡도를 혼동하지 마세요. 이 학습본은 선택과 갱신을 그대로 관찰할 수 있는 배열 탐색 구현입니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function primForest(n, edges) {
  if (!Number.isInteger(n) || n < 0 || !Array.isArray(edges)) {
    throw new RangeError('정점 수와 간선 배열을 확인하세요.');
  }
  const graph = Array.from({length:n}, () => []);
  let magnitude = 0;
  for (const edge of edges) {
    if (!Array.isArray(edge) || edge.length !== 3) throw new TypeError('간선은 [u,v,w]입니다.');
    const [u,v,w] = edge;
    if (![u,v].every(x => Number.isInteger(x) && x >= 0 && x < n)) {
      throw new RangeError('간선 정점 번호가 범위를 벗어났습니다.');
    }
    magnitude += Math.abs(w);
    if (!Number.isSafeInteger(w) || !Number.isSafeInteger(magnitude)) {
      throw new RangeError('가중치와 절댓값 합은 안전한 정수여야 합니다.');
    }
    graph[u].push([v,w]);
    graph[v].push([u,w]);
  }
  const visited = Array(n).fill(false);
  const key = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);
  const chosen = [];
  let components = 0, weight = 0;
  for (let start = 0; start < n; start++) {
    if (visited[start]) continue;
    components++;
    key[start] = 0;
    while (true) {
      let u = -1;
      for (let v = 0; v < n; v++) {
        if (!visited[v] && key[v] < Infinity && (u === -1 || key[v] < key[u])) u = v;
      }
      if (u === -1) break;
      visited[u] = true;
      if (parent[u] !== -1) {
        chosen.push([parent[u],u,key[u]]);
        weight += key[u];
      }
      for (const [v,w] of graph[u]) {
        if (!visited[v] && w < key[v]) { key[v] = w; parent[v] = u; }
      }
    }
  }
  return { connected: n === 0 || components === 1, components, weight, edges: chosen };
}

console.log(JSON.stringify(primForest(4,[[0,1,4],[0,2,3],[1,2,1],[1,3,2],[2,3,4]])));
console.log(JSON.stringify(primForest(4,[[0,1,2],[2,3,3]])));

node algorithm-prim-minimum-spanning-forest.mjs

{"connected":true,"components":1,"weight":6,"edges":[[0,2,3],[2,1,1],[1,3,2]]}
{"connected":false,"components":2,"weight":5,"edges":[[0,1,2],[2,3,3]]}

비용과 적용 범위

정점 V개, 무방향 입력 간선 E개에 대해 선형 최소 후보 탐색 구현의 시간 O(V²+E), 인접 목록과 상태 공간 O(V+E)입니다. 안전한 정수 가중치와 그 절댓값 합을 검사합니다. 연결되지 않은 입력은 connected=false인 최소 신장 숲으로 반환합니다.

직접 확인해 보기

정점 0·1·2·3에 간선 [0,1,2]와 [2,3,3]만 있으면 반환된 총합 5를 최소 신장 트리 비용이라고 불러도 될까요?

함께 읽을 글

• 트리 자료구조 차이: 이진 트리 BST MST 구분하기 — 신장 트리·이진 트리·BST가 서로 다른 기준의 개념임을 먼저 구분합니다.
• 다익스트라의 원리: 거리 완화와 오래된 후보 건너뛰기 — 최단 거리의 누적 완화와 프림의 단일 연결 간선 갱신을 비교합니다.
• JavaScript 그래프 구현: 인접 리스트·인접 행렬 비교와 BFS — 무방향 간선을 양쪽 인접 목록에 담는 표현을 복습합니다.

참고 자료

• Competitive Programmer’s Handbook — 15.3 Prim’s algorithm — 정점 집합을 확장하는 최소 신장 트리 선택과 프림의 원리.