🌱

[JS] 최소 스패닝 트리(MST)


Spanning Tree

Undirected graph에서 스패닝 트리는 그래프의 정점 전부와 간선의 부분집합으로 이루어진 부분 그래프다. 이때 스패닝 트리의 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 트리 형태라는 것은 간선들이 사이클을 이루지 않아야 한다는 중요한 의미를 가진다.

'Minimum spanning tree' 문제는 만들 수 있는 스패닝 트리 중 가중치가 가장 작은 트리를 찾는 문제다. 쉽게 말하면 그래프의 연결성을 유지하는 가장 비용이 적은 트리를 찾는 것이다.

최소 스패닝 트리를 찾는 문제를 풀 수 있는 두 가지 유명한 알고리즘 'Kruskal algorithm'과 'Prim algorithm'을 살펴보자.

Kruskal

크루스칼 알고리즘은 가중치가 작은 간선들부터 하나씩 선택하면서 스패팅 트리를 완성하는 방식이다. 간선들을 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해가면서 스패닝 트리를 만든다. 이때 간선은 사이클이 발생하지 않는 것만 선택한다.

간선을 추가했을 때 이미 추가한 간선과 사이클을 이루는지 확인할 수 있는 효율적인 방법은 disjoint set을 사용하는 것이다.

어떤 간선을 추가했을 때 그래프에 사이클이 생기려면, 간선의 양 끝 점이 같은 컴포넌트에 속할 때다. 따라서 두 간선이 주어졌을 때 이들이 같은 컴포넌트에 속하는지 확인하고, 그렇지 않다면 두 컴포넌트를 합치면 된다.

1/**
2* @param {Array} edges Array with objects that has three properties u(node), v(node), w(weight)
3* @param {Array} selected Empty array to return MST
4* @return {number}
5*/
6function kruskal(edges, selected) {
7 let minimumWeight = 0;
8 const disjointSet = new DisjointSet(edges.length);
9
10 edges.sort((a, b) => a.w - b.w);
11
12 for(let edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
13 let {u, v, w} = edges[edgeIndex];
14 u = disjointSet.find(u); v = disjointSet.find(v);
15 // 이미 u와 v가 연결되어 있을 경우 무시
16 if(u === v) continue;
17 selected.push({ u, v });
18 disjointSet.merge(u, v);
19 minimumWeight += w;
20 }
21
22 return minimumWeight;
23}

위의 쿠르스칼 알고리즘은 간선 목록의 정렬에 걸리는 시간 O(ElgE)O(|E|lg|E|)가 지배하고, 이것이 전체 시간 복잡도가 된다.

Prim

프림 알고리즘은 하나의 시작점에서 출발해서 간선을 하나씩 추가하며 스패닝 트리가 될 때까지 키워가는 방식이다.

각 차례마다 다음으로 추가할 간선을 찾는다. 이때 트리에 속하지 않은 각 정점에 대해, 트리와 이 정점을 연결하는 가장 짧은 간선에 대한 정보를 저장하고(minWeight), 각 정점을 순회하면서 다음에 추가할 정점을 찾아준다. 이런 식으로 구현하면 간선이 아닌 정점을 순회하기 때문에 O(V)O(|V|) 시간에 다음에 추가할 간선을 찾을 수 있다.

정점을 찾는 작업은 O(V)O(|V|) 시간에 할 수 있고, 모든 간선은 uv를 트리에 추가될 때 각각 한 번씩, 총 두 번씩 검사되므로 전체 시간복잡도는 O(V2+E)O(|V|^2+|E|)가 된다.

1/**
2* @param {number} V The number of vertices
3* @param {Array} adjList Array with Array of object with properties v(vertex), w(weight)
4* @param {Array} selected Empty array to return MST
5* @return {number}
6*/
7function prim(V, adjList, selected) {
8 // 해당 정점이 트리에 포함되어 있나?
9 const added = new Array(V).fill(false);
10 // 트리에 인접한 간선 중 해당 정점에 닿는 최소 간선의 정보를 저장한다.
11 const minWeight = new Array(V).fill(Infinity);
12 const parent = new Array(V).fill(-1);
13 // 가중치의 합을 저장할 변수
14 let ret = 0;
15 // 0번 정점을 시작점으로: 항상 트리에 가장 먼저 추가한다.
16 minWeight[0] = parent[0] = 0;
17 for (let iter = 0; iter < V; iter++) {
18 // 다음에 트리에 추가할 정점 u를 찾는다.
19 let u = -1;
20 for (let v = 0; v < V; v++) {
21 if (!added[v] && (u === -1 || minWeight[u] > minWeight[v])) u = v;
22 }
23 // (parent[u], u)를 트리에 추가한다.
24 if (parent[u] !== u) selected.push({ u, v: parent[u] });
25 ret += minWeight[u];
26 added[u] = true;
27 // u에 인접한 간선 (u, v)들을 검사한다.
28 for (let i = 0; i < adjList[u].length; i++) {
29 let v = adjList[u][i].v, weight = adjList[u][i].w;
30 if (!added[v] && minWeight[v] > weight) {
31 parent[v] = u;
32 minWeight[v] = weight;
33 }
34 }
35 }
36 return ret;
37}

참조: 알고리즘 문제 해결 전략 2