크루스칼 알고리즘은 가중 그래프 내에서 최소 비용으로 모든 노드를 연결하는 알고리즘이다.
이 알고리즘을 통해 만들어진 그래프는 '하나의 루트 노드'로, '최소 비용'으로, '모든 노드를 연결'하는 최소 비용 신장 트리(minimum spanning tree, MST)이다.

크루스칼 알고리즘은 Union-Find알고리즘의 원리를 응용하여 구현할 수 있으며, 최소 비용 신장 트리 알고리즘의 또 다른 종류인 프림 알고리즘(Prim's Algorithm)보다 범용성이 높다.

(자료 출처 안경잡이 개발자)

크루스칼 알고리즘의 동작 원리

위와 같이 양의 가중치를 가진 그래프가 있다.

'최소 비용 신장 트리'는
'최소 비용'이어야 한다. 따라서 비용이 최소가 되도록 트리에 포함시킨다.
'신장'이어야 한다. 모든 노드가 연결될 때까지 반복한다.
'트리'여야 한다. 싸이클이 발생하지 않도록 제약을 넣는다. (애초에 싸이클이 발생하면 최소 비용이 되지 않는다.)

크루스칼 알고리즘의 구현

1. 간선 리스트를 가중치 순으로 정렬한다.
2. 간선 리스트의 가중치가 가장 적은 순으로 Union-Find를 시행한다.
3. Find를 시행했을 때, 이미 같은 부모에 포함되어있는 노드들이라 Union을 시행하지 않고 넘어간다.

아래는 크루스칼 알고리즘의 구현 예시이다.

간선 리스트를 가중치 순으로 정렬한 후,
Union-Find를 시행하며 Union이 진행될 때마다 costs를 answer에 더하고 이싿.

n = 4;
costs = [
  [0, 1, 1],
  [0, 2, 2],
  [1, 2, 5],
  [1, 3, 1],
  [2, 3, 8],
];

function solution(n, costs) {
  var answer = 0;
  const parentArray = Array.from({ length: n }, (e, i) => i);
  costs.sort((a, b) => a[2] - b[2]);

  function findParent(index) {
    if (parentArray[index] === index) {
      return index;
    }
    return (parentArray[index] = findParent(parentArray[index]));
  }

  costs.forEach((e) => {
    const root1 = findParent(e[0]);
    const root2 = findParent(e[1]);
    if (root1 !== root2) {
      parentArray[root2] = root1;
      answer += e[2];
    }
  });

  return answer;
}

console.log(solution(n, costs)); //4

전체적인 로직이 기존 Union-Find에서 구현한 것과 동일하다. 단, 인접 행렬이나 인접 리스트가 들어와서 별도의 경로 압축이 필요 없는 서로소 집합 문제들과는 달리 크루스칼 알고리즘 문제는 '간선 리스트'를 '가중치를 기준으로 정렬'하여 사용하기에 경로 압축을 사용할 필요가 있다.

// 경로압축 미적용
// Test 1 〉	통과 (0.12ms, 33.4MB)
// Test 2 〉	통과 (0.10ms, 33.4MB)
// Test 3 〉	통과 (0.20ms, 33.4MB)
// Test 4 〉	통과 (0.20ms, 33.4MB)
// Test 5 〉	통과 (0.30ms, 33.5MB)
// Test 6 〉	통과 (0.22ms, 33.5MB)
// Test 7 〉	통과 (0.35ms, 33.5MB)
// Test 8 〉	통과 (0.24ms, 33.6MB)

// 경로압축적용
// Test 1 〉	통과 (0.10ms, 33.4MB)
// Test 2 〉	통과 (0.11ms, 33.5MB)
// Test 3 〉	통과 (0.20ms, 33.4MB)
// Test 4 〉	통과 (0.21ms, 33.4MB)
// Test 5 〉	통과 (0.21ms, 33.5MB)
// Test 6 〉	통과 (0.22ms, 33.4MB)
// Test 7 〉	통과 (0.26ms, 33.6MB)
// Test 8 〉	통과 (0.19ms, 33.5MB)