Prim's Algorithm — 기초부터 실무까지

이 글은 Prim's Algorithm을 처음부터 실무 관점까지 설명합니다. 목표는 코드를 외우는 것이 아니라 어떤 문제를 해결하고, 왜 동작하며, 실제 시스템에서 언제 사용하는지 이해하는 것입니다.

어떤 문제를 해결하나요?

이 글은 Prim's Algorithm을 처음부터 실무 관점까지 설명합니다. 목표는 코드를 외우는 것이 아니라 어떤 문제를 해결하고, 왜 동작하며, 실제 시스템에서 언제 사용하는지 이해하는 것입니다.

핵심 아이디어

문제를 그래프로 표현한 뒤 정점과 간선을 정해진 규칙에 따라 처리해 필요한 구조나 답을 얻습니다.

단계별 동작

1. 문제에서 정점과 간선이 무엇인지 정의합니다.
2. 적절한 그래프 표현 방식을 선택합니다.
3. visited, distance, degree 같은 필요한 상태를 관리합니다.
4. 실제 적용 전에 결과와 edge case를 검증합니다.

JavaScript 예제

function prim(graph, start) {
  const seen = new Set([start]), mst = [], edges = [];
  edges.push(...(graph[start] ?? []).map(([v,w]) => [w,start,v]));
  while (edges.length) {
    edges.sort((a,b)=>a[0]-b[0]);
    const [w,u,v] = edges.shift();
    if (seen.has(v)) continue;
    seen.add(v); mst.push([u,v,w]);
    for (const [to,cost] of graph[v] ?? [])
      if (!seen.has(to)) edges.push([cost,v,to]);
  }
  return mst;
}

실무 활용 예시

• 사용자와 서비스 간 관계 분석
• 소프트웨어 모듈 의존성 관리
• 네트워크 및 통신
• 비즈니스 시스템의 경로와 workflow

시간 및 공간 복잡도

با Heap حدود O(E log V)

언제 사용하나요?

문제 구조와 목표가 이 알고리즘이 해결하도록 설계된 유형과 일치할 때 사용합니다.

언제 적합하지 않나요?

그래프 유형이나 목표가 다르면 무조건 적용하지 마세요. 더 단순하거나 빠른 알고리즘이 있을 수 있습니다.

정리

알고리즘 이름만 보고 선택하지 마세요. 그래프가 방향/무방향인지, 가중/무가중인지, 그리고 목표가 traversal, reachability, shortest path, connectivity, spanning structure, optimization 중 무엇인지 먼저 확인해야 합니다.