[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)

Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

Spanning Tree란?

- 그래프 내의 모든 정점을 포함하는 트리로서 그래프의 최소 연결 부분 그래프 이다.

- 최소 연결이란 간선의 수가 가장 적다는 것이다.

- 가중치는 고려하지 않고 n개의 정점이 n-1개의 간선으로 연결되어 있어야 하고, 사이클을 포함해서는 안된다.

 

Spanning Tree에 Minimum이 붙었다는 것은 최소 즉, 가중치를 간선에 할당한 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이 MST(Minimum Spanning Tree)이다.

특징

1. 간선의 가중치의 합이 최소여야 한다.

2. n개의 정점을 가지는 그래프의 경우 반드시 n-1개의 간선만을 사용해야 한다(가진다).

3. 사이클(출발점으로 다시 돌아올 수 있는 경로) 이 생기면 안된다.

 

'모든 정점을 연결해야함' + '가중치가 존재하며 최소 비용으로 정점을 연결해야 함'

이런 유형의 문제들은 MST로 해결할 수 있다.

MST의 구현방법으로는 Kruscal 알고리즘과 Prim 알고리즘이 있다.

 

1. Kruscal MST 알고리즘

- 크루스칼 알고리즘은 모든 간선에 대해 가장 가중치가 작은 간선부터 연결해주면서 최소 스패닝 트리를 만들어 나가는 알고리즘이다.

- 간선 선택을 기반으로 하는 알고리즘으로서 무조건 최소 간선만을 선택하는 방법이다.

1.1 구현 과정

- 그래프의 간선들을 가중치의 오름차순으로 정렬한다.

- 정렬된 간선들 중 낮은 가중치부터 순서대로 사이클을 형성하지 않도록 간선을 선택한다. 

- 모든 정점이 연결되면 가중치 값을 구해서 계산한다.

1.2 소스 코드

- 백준 1197번 최소 스패닝 트리 문제를 Krusacl 알고리즘으로 해결

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct info {
	int from;
	int to;
	int weight;
}INFO; //시작점, 도착점, 가중치 정보

int parent[10001];
int flag = 0;
long long ans = 0;
vector<info> edge;
int v, e;

bool comp(info d1, info d2){
	return d1.weight < d2.weight;
} // 오름차순 정렬을 위한 함수

int find(int u){
	if (u == parent[u]) 
		return u;

	return parent[u] = find(parent[u]);
}

void merge(int u, int v){ // 사이클 존재 여부 확인 코드
	flag = 0;
	u = find(u);
	v = find(v);

	if (u == v)
		return;
        
	parent[u] = v;
	flag = 1;
}

int main() {
	
	cin >> v >> e;

	for (int i = 0; i < e; i++) {
		cin >> INFO.from >> INFO.to >> INFO.weight;
		edge.push_back(INFO);
	}

	for (int i = 1; i <= v; i++)
		parent[i] = i; //사이클 초기화(부모 정점)

	sort(edge.begin(), edge.end(), comp); // 가중치를 오름차순으로 정렬

	for (int i = 0; i < e; i++){
		merge(edge[i].from, edge[i].to);
        	if (flag) ans += (long long)edge[i].weight;
	}

	cout << ans << '\n';
	return 0;
}

2. Prim MST 알고리즘

- 프림 알고리즘은 하나의 시작점을 잡고 시작점과 연결된 정점들에 대해 가장 가중치가 작은 간선부터 연결해주면서 최소 스패닝 트리를 만들어 나가는 알고리즘을 의미한다.

- 만약 가중치가 작은 간선이 사이클을 형성할 경우 무시하고 다음으로 가중치가 작은 간선을 선택한다.

- 정점 선택을 기반으로 하는 알고리즘으로 연결된 정점들에 대한 간선들로서 정점을 연결한다.

2.1 구현과정

- 임의의 시작 정점을 선택한 뒤 연결된 간선 중 가중치가 최소인 간선을 선택한다.

- 간선에 연결된 정점들 중에서 가중치가 최소인 간선을 먼저 선택하며 정점들을 연결한다. 단 사이클이 생기는 간선의 경우 선택하지 않는다.

- 위의 과정을 n-1개의 간선을 가질 때까지 반복한다.

2.2 소스코드

- 백준 1197번 최소 스패닝 트리 문제를 Prim 알고리즘으로 해결

#include <iostream>
#include <vector>
#include <queue>

#define MAX 10001

using namespace std;

vector<pair<int, int>> v[MAX];
bool visit[MAX];
int ans = 0;

void prim(int start){
	visit[start] = true;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for (int i = 0; i < v[start].size(); i++){
		int next = v[start][i].first;
		int cost = v[start][i].second;

		pq.push(make_pair(cost, next));
	}

	while (!pq.empty()){
		int now = pq.top().second;
		int now_cost = pq.top().first;

		pq.pop();

		
		if (visit[now]) continue;

		visit[now] = true;

		ans += now_cost;

		for (int i = 0; i < v[now].size(); i++){
			int next = v[now][i].first;
			int next_cost = v[now][i].second;

			pq.push(make_pair(next_cost, next));
		}
	}

}

int main(){
	int V, E;
	cin >> V >> E;

	for (int i = 0; i < E; i++){
		int from, to, val;
		cin >> from >> to >> val;

		v[from].push_back(make_pair(to, val));
		v[to].push_back(make_pair(from, val));
	}

	prim(1);


	cout << ans << '\n';

	return 0;
}

3. 결론

- Kruscal과 Prim 둘중 아무거나 사용해서 풀어도 문제를 해결 할 수 있지만 Kruscal의 경우 간선 중심의 알고리즘, Prim의 경우 정점 중심의 알고리즘이다 보니 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우에 크루스칼 알고리즘이 적합하고 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우는 프림 알고리즘이 적합하다.

Prim의 알고리즘의 시간 복잡도는 O(n^2) 이고

Kruskal 알고리즘의 시간 복잡도는 O(elog₂e) 이다.