신장 트리
주어진 방향성이 없는 그래프의 부분 그래프들 중에서 모든 정점을 포함하는 트리
반드시 연결 그래프여야만 한다
최소 신장 트리(Minimum spanning Tree)
크루스칼 알고리즘
- 간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다
- 현재 선택한 건선이 정점 u, v를 연결하는 간선이라고 할 때 만약 u와 v가 같은 그룹이라면 아무것도 하지 않고 넘어간다. u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다
- 최소 신장 트리에 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;
}
프림 알고리즘
알고리즘의 흐름
- 임의의 정점을 선택해 최소 신장 트리에 추가한다
- 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가한다
- 최소 신장 트리에 V-1개의 간선이 추가될 때 까지 2번을 반복한다
구현
- 임의의 정점을 선택해 최소 신장 트리에 추가하고 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가한다
- 우선순위 큐에서 비용이 가장 작은 간선을 선택한다
- 만약 해당 간선이 최소 신장 트리에 포함된 두 정점을 연결한다면 아무것도 하지 않고 넘어간다. 해당 간선이 최소 신장 트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 해당 간선과 정점v를 최소 신장 트리에 추가 후 정점 v와 최소 신장 트리에 포함되지않는 정점을 연결하는 모든 간선을 우선순위 큐에 추가한다
- 최소 신장 트리에 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;
}
프림 알고리즘 버전
'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글
| [0x1D] 다익스트라 알고리즘 (0) | 2022.08.10 |
|---|---|
| [0x1C] 플로이드-워셜 알고리즘 (0) | 2022.08.10 |
| [0x1A] 위상 정렬 (0) | 2022.08.08 |
| [0x19] 트리 (0) | 2022.08.08 |
| [0x18] 그래프 (0) | 2022.08.07 |
