[0x1B] 최소 신장 트리

신장 트리

 

 

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

반드시 연결 그래프여야만 한다

 

최소 신장 트리(Minimum spanning Tree)

 

크루스칼 알고리즘

 

1. 간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다
2. 현재 선택한 건선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무것도 하지 않고 넘어간다. u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다
3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료하고 그렇지 않다면 그 다음으로 비용이 적은 간선을 선택한 후 2번 과정을 반복한다

 

간선의 가중치가 낮은순으로 정렬 후 Union-Find를 이용하여 간선을 추가해나간다.

간선의 개수가 v-1개가 됐다면 최소 신장 트리가 만들어진다.

시간복잡도는 O(ElogE)이다.

int find_root(int x)
{
	if (p[x] < 0) return x; // 루트는 자기 자신이 부모노드이다
	return p[x] = find_root(p[x]);
}

int union_root(int a, int b)
{
	a = find_root(a);
	b = find_root(b);
	if (a == b) return false;
	if (p[a] == p[b]) p[a]--; // union by rank
	if (p[a] < p[b]) p[b] = a;
	else p[a] = b;
	return true;
}

 

프림 알고리즘

 

알고리즘의 흐름

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

 

구현

1. 임의의 정점을 선택해 최소 신장 트리에 추가하고 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가한다
2. 우선순위 큐에서 비용이 가장 작은 간선을 선택한다
3. 만약 해당 간선이 최소 신장 트리에 포함된 두 정점을 연결한다면 아무것도 하지 않고 넘어간다. 해당 간선이 최소 신장 트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 해당 간선과 정점v를 최소 신장 트리에 추가 후 정점 v와 최소 신장 트리에 포함되지않는 정점을 연결하는 모든 간선을 우선순위 큐에 추가한다
4. 최소 신장 트리에 V-1개의 간선이 추가될 때 까지 2, 3번을 반복한다

 

시간복잡도는 크루스칼 알고리즘과 마찬가지로 O(ElogE)이다.

#define X first
#define Y second

int v, e;
vector<pair<int, int>> adj[10005]; // 비용, 정점의 번호
bool chk[10005];
int cnt = 0;
priority_queue<	tuple<int, int, int>,
	vector<tuple<int, int, int>>,
	greater<tuple<int, int, int>>> pq;

chk[1] = 1;
for (auto& nxt : adj[1])
	pq.push({ nxt.X, 1, nxt.Y });
while (cnt < v - 1) {
	int cost, a, b;
	tie(cost, a, b) = pq.top(); pq.pop();
	if (chk[b]) continue;
	cout << cost << ' ' << a << ' ' << b << '\n';
	chk[b] = 1;
	cnt++;
	for (auto& nxt : adj[b]) {
		if (!chk[nxt.Y])
			pq.push({ nxt.X, b, nxt.Y });
	}
}

 

 

연습 문제

 

1197: 최소 스패닝 문제

#include <bits/stdc++.h>
using namespace std;

vector<int> p(10001, -1);
tuple<int, int, int> edges[100001];
int v, e, ans, cnt;

int find_root(int x)
{
	if (p[x] < 0) return x; // 루트는 자기 자신이 부모노드이다
	return p[x] = find_root(p[x]);
}

int union_root(int a, int b)
{
	a = find_root(a);
	b = find_root(b);
	if (a == b) return false;
	if (p[a] == p[b]) p[a]--; // union by rank. 트리의 깊이를 조정해줌
	if (p[a] < p[b]) p[b] = a;
	else p[a] = b;
	return true;
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> v >> e;
	for (int i = 0; i < e; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges[i] = {c, a, b};
	}
	sort(edges, edges + e);
	for (int i = 0; i < e; ++i)
	{
		int a, b, c;
		tie(c, a, b) = edges[i];
		if (!union_root(a, b)) continue;
		ans += c;
		cnt++;
		if (cnt >= v - 1) break;
	}
	cout << ans;

	return 0;
}

 

크루스칼 알고리즘 버전

이코테에서 습득했던 구현과 조금 달라서 매치시키는데 이해가 좀 많이걸렸음

이코테 및 다른사람들의 코드를 보면 find의 조건문이 p[x] < 0이 아닌 p[x] != x (혹은 p[x] == x)로 되어있는데 무슨차이가 있냐면 전자는 각 정점의 루트노드를 선언과 동시에 -1로 초기화 시켜서 0 미만인 경우 해당 정점이 루트라는걸 알아내는 것이고 후자는 중간에 각 노드의 루트노드를 자기 자신으로 초기화 시키는 부분이 추가되어있다.

구현상의 차이가 있을뿐 결과는 똑같이 나온다.

 

추가로 union에서의 if(p[a] == p[b]) p[a]--; 이부분은 트리가 균등하지 않게 깊어지는 경우 성능 하락이 발생하는것을 방지해주는 코드이다. 없어도 시간복잡도는 로그스케일로 나오긴 한다

 

 

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int v, e, ans;
vector<pair<int, int>> adj[10005]; // 비용, 정점의 번호
bool chk[10005];
int cnt = 0;
priority_queue<	tuple<int, int, int>,
	vector<tuple<int, int, int>>,
	greater<tuple<int, int, int>>> pq;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> v >> e;
	for (int i = 0; i < e; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ c, b });
		adj[b].push_back({ c, a });
	}
	chk[1] = true;
	for (auto& nxt : adj[1])
		pq.push({ nxt.X, 1, nxt.Y });

	while (cnt < v - 1)
	{
		int a, b, c;
		tie(c, a, b) = pq.top(); pq.pop();
		if (chk[b]) continue;
		chk[b] = true;
		ans += c;
		cnt++;
		for (auto& nxt : adj[b]) {
			if (!chk[nxt.Y])
				pq.push({ nxt.X, b, nxt.Y });
		}
	}

	cout << ans;

	return 0;
}

 

프림 알고리즘 버전