MST (Minimum Spanning Tree)
MST란 최소 신장 트리(최소 스패닝 트리)를 뜻한다. 먼저 신장 트리(스패닝 트리)란 주어진 그래프에서 모든 정점을 포함하면서 간선의 수가 가장 적은 그래프를 뜻한다. 이 때, 사이클이 존재하면 안된다.
그리고 이 스패닝 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 그래프를 최소 스패닝 트리라고 한다. 즉 V개의 정점을 갖는 그래프는 V-1개의 간선으로 이루어진 최소 스패닝 트리를 가진다.
이러한 최소 스패닝 트리는 도시들 끼리의 특정한 망(도로, 통신 등)을 구축할 때, 비용을 최소화하기 위해 사용된다. 그리고 MST는 여러 개가 존재할 수 있지만 그 가중치 합의 최솟값은 단 하나이다.
Disjoint-Set
Disjoint-Set은 UnionFind-Set이라고도 부른다. 어떤 집합 모임에 대하여, 특정 원소가 어느 집합에 속하는 지와 두 집합을 합치는 연산을 빠르게 하기 위한 자료구조의 일종이다. Disjoint
-set은 트리를 통해 집합을 나타내며 자신의 부모만을 저장하는 특수한 형태를 갖는다.
Disjoint-Set은 아래의 두 가지 연산을 제공한다.
- Union: 두 집합을 합친다.
- Find: 해당 원소가 속한 집합을 찾는다.
일반적 Disjoint-Set구현
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
vector<int> p;
void init(int n) {
p.resize(n + 1);
for (int i = 0; i < p.size(); i++) {
p[i] = i;
dep[i] = 0;
}
}
// 시간 복잡도 O(N)
int Find(int x) {
if (x == p[x])
return p[x];
return Find(p[x]);
}
// 시간 복잡도 O(N)
bool Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x != y) {
p[y] = x;
return true;
}
return false;
}
};Disjoint-Set 최적화 (유니온 바이 랭크)
Union시 두 집합 중, 깊이가 더 깊은 쪽에 더 작은 깊이를 가진 트리를 합친다. 즉 깊이가 깊은 트리의 루트가 깊이가 작은 트리의 루트가 된다.
Find시 Find를 수행하며 만난 모든 값의 부모 노드를 root로 만든다. 이러한 방식을 경로 압축이라고 한다.
이 경우 Uion, Find의 시간복잡도는 O(log N)이 된다.
Disjoint-Set 최적화 (유니온 바이 랭크) 구현
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
vector<int> p;
vector<int> dep;
void init(int n) {
p.resize(n + 1);
dep.resize(n + 1);
for (int i = 0; i < p.size(); i++) {
p[i] = i;
dep[i] = 0;
}
}
// 시간 복잡도 O(log N)
int Find(int x) {
if (x == p[x])
return p[x];
return p[x] = Find(p[x]);
}
// 시간 복잡도 O(log N)
bool Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x != y) {
if (dep[x] < dep[y]) {
p[x] = y;
}
else if (dep[y] < dep[x]) {
p[y] = x;
}
else {
++dep[x];
p[y] = x;
}
return true;
}
return false;
}
};Kruskal algorithm
MST를 찾기 위한 알고리즘 중 하나로 아래와 같이 동작한다.
- 모든 간선 중 가중치가 최소인 간선을 선택
- 해당 간선을 그래프에 추가하였을 때, 싸이클이 생기지 않으면 추가
- 싸이클이 생겼을 경우 추가하지 않고 Pass
그래프가 여러 곳에서 생겨져 나오고 그것들이 이어져 나가기 때문에 싸이클을 효율적으로 찾을 수 있는 방법이 필요하다. 이때 사용하는 방법이 UnionFind이다.
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
vector<int> p;
vector<int> dep;
public :
void init(int n) {
p.resize(n + 1);
dep.resize(n + 1);
for (int i = 0; i < p.size(); i++) {
p[i] = i;
dep[i] = 0;
}
}
int Find(int x) {
if (x == p[x])
return p[x];
return p[x] = Find(p[x]);
}
bool Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x != y) {
if (dep[x] < dep[y]) {
p[x] = y;
}
else if (dep[y] < dep[x]) {
p[y] = x;
}
else {
++dep[x];
p[y] = x;
}
return true;
}
return false;
}
};
struct EDGE {
int from, to, w;
};
vector<EDGE> edge;
int kruskal(vector<EDGE>& ans, int v) {
int wSum = 0;
sort(edge.begin(), edge.end(), [](EDGE e1, EDGE e2) {
return e1.w < e2.w;
});
UnionFind d;
d.init(v);
for (int i = 0; i < edge.size(); ++i) {
if (d.Union(edge[i].from, edge[i].to)) {
wSum += edge[i].w;
ans.push_back(edge[i]);
}
}
return wSum;
}Prim algorithm
MST를 찾기 위한 알고리즘 중 하나로 아래와 같이 동작한다.
- MST에 속한 정점의 집합을 V라 가정
- V에 임의의 정점 하나를 추가
- V에 속한 정점들과 V에 속하지 않은 정점들을 연결하는 간선 중 가장 짧은 간선 추가
Kruskal algorithm과 달리 항상 V에 속한 정점과 V에 속하지 않은 정점을 연결하므로 싸이클을 찾기 위해 UnionFind를 사용할 필요없다. 즉 특정 정점 x가 V에 속해있는지 아닌 지만 확인하면 된다.
#include <bits/stdc++.h>
using namespace std;
struct EDGE {
int to, w;
};
vector<EDGE> adj[101010];
bool chk[101010];
bool operator < (EDGE e1, EDGE e2) {
return e1.w > e2.w;
}
int prim(vector<EDGE>& ans, int v) {
int wSum = 0;
priority_queue<EDGE> pq;
chk[1] = 1;
for (int i = 0; i < adj[1].size(); ++i)
pq.push(adj[1][i]);
while (pq.size()) {
int curTo = pq.top().to;
int curW = pq.top().w;
pq.pop();
if (chk[curTo])
continue;
chk[curTo] = 1;
wSum += curW;
ans.push_back({ curTo, curW });
for (int i = 0; i < adj[curTo].size(); ++i)
if (!chk[adj[curTo][i].to])
pq.push(adj[curTo][i]);
}
return wSum;
}Topological sort
Topological sort는 위상 정렬을 뜻한다. 위상 정렬은 DAG(Directed Acyclic Graph, 싸이클이 없는 방향 그래프)의 정점들을 간선의 방향을 거스르지 않도록 나열하는 알고리즘이다. 어떠한 일의 순서를 정할 때 사용한다.(수강 신청 선수 과목, 게임 스킬트리등 순서를 정하는 일은 보통 위상 정렬 문제)
위상 정렬은 아래와 같은 과정을 거쳐 이루어진다.
- In-degree(해당 정점으로 들어오는 간선의 갯수)가 0인 정점을 찾는다.
- 해당 정점에서 연결된 정점들의 In-degree를 하나씩 빼준다.
- 이를 반복한다.
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1000];
int ind[1000];
void topologicalSort(int v) {
queue<int> q;
for (int i = 1; i <= v; ++i)
if (ind[i] == 0)
q.push(i);
while (q.size()) {
int cur = q.front(); q.pop();
printf("%d ", cur);
for (int i = 0; i < adj[cur].size(); ++i) {
int next = adj[cur][i];
--ind[next];
if (ind[next] == 0)
q.push(next);
}
}
}