실전 알고리즘 0x1B강 - 최소 신장 트리

최소 신장 트리 ( MST )

[ 정의와 성질 ]

- 주어진 방향성이 없는 그래프의 부분 그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리.

신장 트리

최소 신장 트리

 

[ 크루스칼 알고리즘 ]

- Union Find 알고리즘을 모르면 효율적으로 구현할 수 없다.(Union Find 알고리즘을 알면 프림 알고리즘보다 구현이 쉽다)

1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택

2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무것도 하지 않고 넘어감, u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가

3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료, 그렇지 않다면 그 다음으로 비용이 작은 간선을 선택한 후 2번 과정을 반복

 

- Flood Fill 을 이용한 알고리즘 구현은 간선의 정렬에 O(E logE), 같은 그룹인지 판단하는데 O(VE)의 시간 복잡도가 발생하여 O(E logE + VE)이기 때문에 비효율적이다.

- Union Find를 사용하면 같은 그룹인지 판단하는데 상수시간에 해결 가능하다. 즉, O(E logE)로 구현할 수 있다.

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	
	int v, e;
	// {비용, 정점 1, 정점 2}
	tuple<int, int, int> edge[100005];

	sort(edge, edge + e);
	int cnt = 0;
	for (int i = 0; i < e; i++) {
		int cost, a, b;
		tie(cost, a, b) = edge[i];
		if (!is_diff_group(a, b)) continue;
		cout << cost << ' ' << a << ' ' << b;
		cnt++;
		if (cnt == v - 1) break;
	}

}

- 백준 1197번 : https://www.acmicpc.net/problem/1197

[ 프림 알고리즘 ]

- 우선순위 큐를 이용하여 구현할 수 있다.

1. 임의의 정점을 선택해 최소 신장 트리에 추가

2. 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가

3. 최소 신장 트리에 V-1개의 간선이 추가될 때 까지 2번 과정을 반복

 

- 구현

1. 임의의 정점을 선택해 최소 신장 트리에 추가, 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가

2. 우선순위 큐에 비용이 가장 작은 간선을 선택

3. 만약 해당 간선이 최소 신장 트리에 포함된 두 정점을 연결한다면 아무것도 하지 않고 넘어감, 해당 간선이 최소 신장 트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 해당 간선과 정점 v를 최소 신장 트리에 추가 후 정점 v과 최소 신장 트리에 포함되지 않는 정점을 연결하는 모든 간선을 우선순위 큐에 추가

4. 최소 신장 트리에 V-1개의 간선이 추가될 때 까지 2, 3번 과정을 반복

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

 

[ 연습 문제 ]