[Algorithm Tech] 최소 신장 트리(MST, Minimum Spanning Tree)

* MST란?

Minimum Spanning Tree의 약자로, 직역하면 최소 신장 트리라고 불린다.

Spanning Tree는 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.

앞에 Minimum을 붙이면 각 간선의 가중치가 다른 경우 최소의 가중치로 연결하여 모든 정점을 방문하는 것을 말한다.

즉, MST에서는 간선의 가중치가 최소로 모든 정점을 방문해야하며 사이클이 생겨서는 안된다.

MST에는 크게 Kruskal(크루스칼) 알고리즘과 Prim(프림) 알고리즘이 존재한다.

* 크루스칼 알고리즘 (+Union-Find)

1. 간선을 가중치에 따라 오름차순으로 정렬한다. (Comparable 사용)

2. 가장 가중치를 가지는 간선을 첫번째 간선으로 선택한다.

3. 가중치가 작은 간선을 선택한다.

4. 선택한 간선과 이전에 선택한 간선이 사이클을 이루는지 확인한다. (Union-Find(Disjoint-Set) 사용)

Union-Find 자료구조에서 Disjoint-Set 확인 방법은 다음과 같다.

1. 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화 합니다. 

2. Union (합치기) 연산 : 두 원소 a, b 가 주어질 때, 이들이 속한 두 집합을 하나로 합칩니다. 

3. Find (찾기) 연산 : 어떤 원소 a 가 주어질 때, 이 원소가 속한 집합을 반환합니다. 

즉, disjoint를 통해 같은 집합여부를 확인할 수 있다.

이를 소스코드로 표현하면 다음과 같다.

// Disjoint 초기화
int[] disjoint = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
    disjoint[i] = i;        //disjoint[i]에는 부모의 정점의 번호를 
}
 
// Disjoint Find
public static int find(int x) {
    if (disjoint[x] == x) return x;
    else return disjoint[x] = find(disjoint[x]);
}
 
//Disjoint Union
int x = find(u);        //find
int y = find(v);        //find
if (x != y) {           //union
    disjoint[x] = y;
}

백준/1922 :: 네트워크 연결 문제

백준/1922 :: 네트워크 연결 풀이

* 프림 알고리즘 

1. 가중치가 낮은 간선을 선택한다.

2. 선택한 간선과 인접한 간선 중에서, 사이클을 생성하지 않는 간선 중에서 가중치가 작은 간선을 선택한다. (현재 간선의 가중치를 추가하면 다익스트라)

3. 위 과정을 반복하여 n-1개의 간선을 선택한다.

위 과정을 거치기 때문에 간선을 선택할 때마다 트리의 형태가 유지된다. (보통 우선순위큐를 이용하여 BFS로 구현한다.)

프림 알고리즘은 다익스트라(Dijkstra) 개념과 같이 이해하는게 편리하다.

cf) 프림 알고리즘 : MST를 만들 때 사용하는 알고리즘으로 BFS처럼 선마다 최소 가중치를 찾아 연결하는 방법

다익스트라 알고리즘 : 시작 정점 x에서 도착 정점 y까지 최단거리로 이동하는 방식

// 프림 알고리즘    => 연결된 간선들 중 최소 가중치만 구한다.
pq.add(new Edge(e.v, edge[e.v].get(i).v, edge[e.v].get(i).w));
 
// 다익스트라 알고리즘    => 현재 가중치를 계속 더해야 한다.
pq.add(new Edge(e.v, edge[e.v].get(i).v, edge[e.v].get(i).w + e.w));