[알고리즘/그래프] 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘(Kruskal Algorithm)이란?

---

최소 비용으로 모든 노드를 연결하기 위해서 사용하는 알고리즘으로 대표적인 최소 신장 트리(MST, Minimum Spanning Tree)를 만드는 대표적인 알고리즘이다. 가장 적은 비용(weight)을 탐욕적(Greedy Algorithm)으로 확인하여 가장 적은 비용으로 사이클이 발생하지 않게 모든 노드를 연결한다.

 

시간복잡도는  O(E log E)이다.

• 간선을 가중치순으로 정렬하므로 E log E만큼의 시간이 소요된다. (=퀵정렬의 시간 복잡도)
• 반복문에서 V-1만큼의 시간이 소요된다.

최소 신장 트리(MST, Minimum Spanning Tree)란?

• 신장 트리(Spanning Tree): 그래프의 모든 정점을 연결하고 사이클이 없는 그래프로 신장 트리의 간선 수는 노드 개수 - 1개이다.
• 최소 신장 트리(MST, Minimum Spanning Tree): 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리이다.

이미지 출처: https://i0.wp.com/algorithms.tutorialhorizon.com/files/2018/05/Minimum-Spanning-Tree-basics-1.png?ssl=1

 

구현 방법

1. 가중치가 작은 순서대로 그래프의 간선을 오름차순으로 정렬한다.
2. 정렬된 순서대로(비용이 적은 간선을 순서대로) 그래프에 포함시킨다. 이 때 Union-Find 알고리즘을 사용하여 사이클이 발생했는지 (같은 부모를 가지는지) 확인한다.
3. 사이클이 발생된 경우 해당 간선을 그래프에 포함시키지 않는다.

구현 코드

const { findParent, unionParent } = require('./unionFind');
class Edge {
  constructor(v1, v2, weight) {
    this.edge = [v1, v2];
    this.weight = weight;
  }
}

const matrix = [];

matrix.push(new Edge(1, 7, 12));
matrix.push(new Edge(1, 4, 28));
matrix.push(new Edge(1, 2, 67));
matrix.push(new Edge(1, 5, 17));
matrix.push(new Edge(2, 4, 24));
matrix.push(new Edge(2, 5, 62));
matrix.push(new Edge(3, 5, 20));
matrix.push(new Edge(3, 6, 37));
matrix.push(new Edge(4, 7, 13));
matrix.push(new Edge(5, 6, 45));
matrix.push(new Edge(5, 7, 73));

// 1. 간선의 가중치로 오름차순 정렬
matrix.sort((a, b) => a.weight - b.weight);

// 2. 각 정점이 포함된 그래프(부모)가 어디인지 저장
let parent = [];

// 3. 자기 자신을 가리키도록 초기화
for (let i = 0; i < 9; i++) {
  parent[i] = i;
}

// 4. 사이클이 발생하지 않는 경우 그래프에 포함
let sum = 0; // 거리의 합
for (let i = 0; i < matrix.length; i++) {
  if (!findParent(parent, matrix[i].edge[0], matrix[i].edge[1])) {
    sum += matrix[i].weight;
    unionParent(parent, matrix[i].edge[0], matrix[i].edge[1]);
  }
}

console.log(sum);