JavaScript로 이해하는 크루스칼 알고리즘 (Minimum Spanning Tree)

크루스칼 알고리즘이란?

"크루스칼 알고리즘(Kruskal's Algorithm)"은 그래프 이론에서 "최소 신장 트리(Minimum Spanning Tree, MST)"를 찾기 위해 널리 사용되는 대표적인 "그리디 알고리즘"입니다. 최소 신장 트리는 주어진 모든 정점을 연결하면서, 간선의 전체 가중치 합이 최소가 되는 트리입니다.

크루스칼 알고리즘은 모든 간선을 가중치 기준으로 정렬한 다음, 작은 가중치부터 차례대로 간선을 선택해나가되, 사이클을 만들지 않도록 관리합니다. 이 과정에서 "사이클 여부 확인"을 위해 "Union-Find(유니온-파인드)" 자료구조가 사용됩니다.

---

핵심 절차

크루스칼 알고리즘은 다음과 같은 단계를 따릅니다:

1. 간선 정렬: 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬합니다.
2. Union-Find 초기화: 각 정점이 자기 자신을 부모로 가지는 배열을 생성합니다.
3. 사이클 방지: 정렬된 간선을 하나씩 확인하면서, 해당 간선을 추가했을 때 사이클이 발생하지 않으면 MST에 포함시킵니다.
4. 반복 종료 조건: MST에는 항상 정점 수 - 1개의 간선만 포함됩니다. 이 조건을 만족하면 알고리즘을 종료합니다.

012345678910

---

JavaScript 예제 코드

Union-Find 자료구조 구현

// 부모 노드를 찾는 함수 (경로 압축 포함)
function find(parent, x) {
  if (parent[x] !== x) {
    parent[x] = find(parent, parent[x]); // 재귀적으로 부모를 찾아가며 경로 압축
  }
  return parent[x];
}

// 두 노드를 하나의 집합으로 합치는 함수
function union(parent, a, b) {
  const rootA = find(parent, a);
  const rootB = find(parent, b);
  if (rootA !== rootB) {
    parent[rootB] = rootA; // 하나의 트리에 병합
  }
}

크루스칼 알고리즘 본체

function kruskal(n, edges) {
  // 간선을 가중치 기준으로 정렬
  edges.sort((a, b) => a[2] - b[2]);

  const parent = Array.from({ length: n }, (_, i) => i);
  const mst = []; // MST에 포함되는 간선들
  let totalCost = 0; // 최소 비용 누적

  for (let [u, v, weight] of edges) {
    if (find(parent, u) !== find(parent, v)) {
      union(parent, u, v); // 사이클이 없으므로 간선 추가
      mst.push([u, v, weight]);
      totalCost += weight;
    }
  }

  return { mst, totalCost };
}

// 예시 실행
const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4]
];

const result = kruskal(4, edges);
console.log("MST Edges:", result.mst);
console.log("Total Cost:", result.totalCost);

---

실행 결과 예시

MST Edges: [ [ 2, 3, 4 ], [ 0, 3, 5 ], [ 0, 1, 10 ] ]
Total Cost: 19

---

시간 및 공간 복잡도

• 시간 복잡도: O(E log E)
  • E는 간선의 개수. 간선 정렬에 O(E log E), Union-Find 연산은 거의 O(1)에 가까움
• 공간 복잡도: O(V)
  • V는 정점 수. Union-Find를 위한 배열 크기만큼 공간이 필요

---

프림 알고리즘과의 비교

항목	크루스칼 알고리즘	프림 알고리즘
접근 방식	간선 중심(edge-based)	정점 중심(vertex-based)
주요 자료구조 사용	Union-Find	Min-Heap 또는 인접 리스트
희소 그래프에서의 효율성	뛰어남	다소 떨어질 수 있음
구현 난이도	비교적 간단	Heap 연산이 복잡할 수 있음

---

실전 활용 사례

• 통신 네트워크 구축: ISP, 통신사 등의 인프라 설계 시 최소 비용으로 노드 연결
• 도로망 설계: 도로 공사 시 예산 내에서 도시들을 연결할 때 사용
• 전력망 구성: 전기 공급망을 효율적으로 설계하기 위한 그래프 모델링
• 지리 기반 애플리케이션: 지도상의 경로 최소 연결 구조 구현

---

마무리 및 CTA

"크루스칼 알고리즘"은 그래프의 구조를 최소 비용으로 연결할 수 있도록 해주는 매우 실용적인 알고리즘입니다. "그리디 전략"과 "Union-Find" 개념을 함께 익히는 데 효과적이며, 그래프 문제에서 기본적으로 요구되는 핵심 전략 중 하나입니다.

정점 중심으로 탐색하는 "프림 알고리즘"과 병행하여 학습하면, 다양한 그래프 상황에 따라 최적의 알고리즘을 선택하는 안목을 기를 수 있습니다.

추천 학습 자료:

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

위 자료들은 시각적으로 구조를 파악하고 알고리즘 흐름을 따라가기에 좋은 참고 리소스입니다. 단계별로 "Union-Find" 동작이 어떻게 수행되는지 직접 확인해보며 학습하면, MST 설계에 대한 이해가 훨씬 깊어질 수 있습니다.