MST

참고자료

https://blog.encrypted.gg/1024

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

 

1. 최소 스패닝(신장) 트리

---

신장 트리란

• 주어진 방향성이 없는 그래프의 부분 그래프들 중에서 모든 정점을 포함하는 트리를 말한다.
• 부분 그래프란 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 그래프를 말한다.
• 참고) 트리는 무방향이면서 사이클이 없는 연결 그래프

그림 예시

• 신장트리가 아닌 예시는 모든 정점을 포함하지 않거나, 사이클이 존재하기 때문에 신장 트리가 아니다.

최소 신장 트리

• 신장 트리 중에서 간선의 "합이 최소"인 트리를 의미한다.
• 최소신장트리는 동일한 그래프에서 한개가 아닐수 있다.

 

 

2. 구현 알고리즘

---

2 - 1. 크루스칼 알고리즘

가장 비용이 낮은 간선부터 시작해 간선을 크기 순으로 살펴보며, 서로 떨어져 있던 정점들을 합쳐나가는 방식

유니온 파인드 기법, 그리디 방식 사용

 

동작 방식

• 간선의 크기를 오름차순으로 정렬, 제일 낮은 비용의 간선 선택
• 현재 선택한 간선이 연결한 정점이 같은 그룹이라면 아무것도 하지않고 넘어감
• 연결한 정점이 다른 그룹이라면, 같은 그룹으로 만들고 현재 선택한 간선을 최소신장트리에 추가
• 최소신장트리에 v-1개의 간선이 추가되면 과정을 종료, 그렇지 않으면 다음으로 비용이 작은 간선을 선택한 후 위의 과정 반복

템플릿 코드 ( https://www.acmicpc.net/problem/1197 )

• find와 diff_group 함수가 유니온 파인드 내용
• 유니온 파인드를 통해 같은 그룹인지 아닌지를 체크

 

#include <iostream>
#include <tuple>
#include <algorithm>
#include <vector>
using namespace std;

int v, e;
tuple<int, int, int> edge[100005]; //비용 정점1 정점2
vector<int> p(10005, -1);

int find(int x)
{
	if (p[x] < 0)
		return x;
	return p[x] = find(p[x]);
}

bool diff_group(int u, int v)
{
	u = find(u);
	v = find(v);

	if (u == v)
		return 0;
	if (p[u] == p[v])
		p[u]--;
	if (p[u] < p[v])
		p[v] = u;
	else
		p[u] = v;
	return 1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> v >> e;

	for (int i = 0; i < e; ++i)
	{
		int a, b, cost;
		cin >> a >> b >> cost;
		edge[i] = { cost,a,b };
	}

	sort(edge, edge + e);
	int cnt = 0;
	int ans = 0;

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

 

2 - 2. 프림 알고리즘

동작 과정

• 임의의 정점을 선택해 최소 신장 트리에 추가
• 최소 신장 트리에 포함된 정점과 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가
• 최소신장트리에 간선이 v-1이 될때까지 반복

이 알고리즘을 구현하기 위해서는 우선순위큐를 사용하여, 효율적으로 구현해야 한다. (다익스트라와 유사한 방식)

 

템플릿 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int v, e;
vector<pair<int, int>> adj[10005]; //비용, 정점 번호
bool check[10005]; //최소신장트리에 포함된 정점
int cnt = 0;
int ans = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> v >> e;
	for (int i = 0; i < e; ++i)
	{
		int a, b, cost;
		cin >> a >> b >> cost;

		adj[a].push_back({ cost, b });
		adj[b].push_back({ cost, a });
	}

	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>> > pq;

	check[1] = 1; //1을 시작으로
	for (auto nxt : adj[1])
		pq.push({ nxt.first, 1, nxt.second });

	while (cnt < v - 1)
	{
		int cost, a, b;
		tie(cost, a, b) = pq.top();
		pq.pop();

		if (check[b])
			continue;
		ans += cost;
		check[b] = 1;
		cnt++;
		for (auto nxt : adj[b])
		{
			if (!check[nxt.second])
				pq.push({ nxt.first, b, nxt.second });
		}
	}
	cout << ans;
}

 

 

3. 더 풀어보기

---

https://www.acmicpc.net/problem/1368

 

https://www.acmicpc.net/problem/1647