최소 스패닝 트리 / 최소 신장 트리 (MST)

최소 스패닝 트리 / 최소 신장 트리

(MST : Minimum Spanning Tree)

by Kruskal Algorithm & Prim Algorithm

---

  정의 

  최소 스패닝 트리(최소 신장 트리, MST : Minimum Spanning Tree)란, 모든 노드들이 가중치가 있는 무방향 간선에 연결이 되어있을 때, 모든 노드들을 연결하는 방법 중 사이클이 없으면서 가중치의 합이 최소가 되는 트리를 의미한다.

  좌측과 같은 그래프가 있다고 할 때, 최소 스패닝 트리은 우측의 빨간 간선들로 이루어진 그래프가 된다. 완성된 최소 스패닝 트리는 모든 노드들이 전부 연결이 되어있으며, 사이클이 존재하지 않는다. 또한 V개의 정점을 가진 그래프라고 할 때, 최소 스패닝 트리는 V - 1 개의 간선을 가진 트리가 된다.

---

  설명 

  최소 스패닝 트리 알고리즘은 많은 알고리즘에서 쓰일 수 있다. 예를 들어서 도로가 존재하는 모든 도시들끼리 이동할 수 있도록 되어 있으면서, 총 도로의 길이가 최소가 되도록 할 때, 모든 건물들을 연결하는 전화선의 길이가 최소가 되도록 케이블 망을 구성할 때 등에서 사용된다.

  최소 스패닝 트리를 구하기 위해 사용되는 알고리즘은 대표적으로 Kruskal algorithm, Prim algorithm 가 있다.

---

 크루스칼 알고리즘 (Kruskal algorithm)  

  크루스칼 알고리즘은 계속해서 가중치의 값이 가장 작은 간선을 선택하여 트리에 추가를 하는 알고리즘 이다. 단, 선택한 간선이 이미 어느 트리에 포함되어있지 않으면서 그 간선을 추가함으로서 사이클이 형성되지 않아야 한다. 만약 가중치의 값이 같은 간선들이 있다면 임의로 하나를 선택하여 최소 스패닝 트리에 추가를 하면 된다.

  계속해서 선택되지 않은 간선들 중 최소의 가중치를 가지는 간선을 파악하기 위해 우선순위큐를 사용할 수 있다. 선택된 간선의 양쪽 두 정점이 같은 트리에 있다면? 지금 선택된 간선을 연결하게 되면 사이클이 발생하게 된다. 즉, 선택된 간선이 최소 스패닝 트리에 추가되기 위해선 두 정점이 서로 다른 트리에 속해있어야 하고, 이를 유니온 파인드 (Union - Find / Disjoint :유니온 파인드 (Union Find, Disjoint set)) 를 통해 알 수 있다.

  크루스칼 알고리즘은 하나의 최소 스패닝 트리를 계속해서 연장해 나가는 것이 아닌, 최소값의 가중치를 가진 간선들을 각자 따로 트리를 만들기 시작해서 점점 그 트리들이 합쳐져 최종적으로 최소 스패닝 트리가 이루어지는 것 이다.

 

0123456

  위 슬라이드로 크루스칼 알고리즘에 따른 그래프의 변화를 표현 해 보았다.

  Kruskal algorithm code 

1197번: 최소 스패닝 트리 (acmicpc.net)

1197번: 최소 스패닝 트리

  최소 스패닝 트리에 대한 기본 문제를 Kruskal algorithm 으로 풀어본 코드이다.

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

using namespace std;
typedef long long ll;

struct N {
	int a;
	int b;
	ll val;
};

bool operator < (N a, N b) {
	return a.val < b.val;
}
bool operator > (N a, N b) {
	return a.val > b.val;
}
bool operator <= (N a, N b) {
	return a.val <= b.val;
}
bool operator >= (N a, N b) {
	return a.val >= b.val;
}
bool operator == (N a, N b) {
	return a.val == b.val;
}

priority_queue<N, vector<N>, greater<N>> q;
vector<int> parent;
ll answer = 0;
int v, e;

int find(int a) {
	if (parent[a] == a) return a;
	else return parent[a] = find(parent[a]);
}

void Union(int a, int b) {
	int pa = find(a);
	int pb = find(b);

	parent[pb] = parent[pa];
}

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

	parent.assign(v + 1, 0);

	for (int i = 1; i <= v; i++) parent[i] = i;

	int a, b, c;
	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		
		q.push({ a, b, c });
	}

	N cur;
	int cura, curb, curVal;

	while (!q.empty()) {
		cur = q.top(); q.pop();

		cura = cur.a;
		curb = cur.b;
		curVal = cur.val;

		if (find(cura) != find(curb)) {
			Union(cura, curb);
			answer += curVal;
		}
	}

	cout << ::answer;
}

---

 프림 알고리즘 (Prim algorithm)  

  이전의 크루스칼 알고리즘은 최소 가중치 간선을 찾음으로써 시작했지만 프림 알고리즘은 임의의 정점 하나를 선택한 후 시작된다. 임의의 정점이 선택된 후 인접한 정점들 중 아직 방문되지 않은 정점이면서 최소 가중치를 가지는 간선을 최소 스패닝 트리에 포함시킨다. 

  프림 알고리즘은 크루스칼 알고리즘과는 달리 하나의 트리를 계속해서 확장을 시켜서 최종적으로 이 트리를 최소 스패닝 트리로 만든다. 그에 따라 계속해서 만들어진 트리의 인접 정점들 중 아직 방문하지 않은 정점이면서 그 정점과의 간선의 가중치 값이 가장 최소인 간선을 트리에 포함시킨다.

  최소 스패닝 트리의 간선의 수는 정점의 수(V) - 1 개 이므로 이 작업을 V - 1 번 진행하면 된다.

0123456

  위 슬라이드로 프림 알고리즘에 따른 그래프의 변화를 표현 해 보았다. vertex A 부터 최소 스패닝 트리를 구현해가기 시작한다.

  Prim algorithm code 

1197번: 최소 스패닝 트리 (acmicpc.net)

1197번: 최소 스패닝 트리

  최소 스패닝 트리에 대한 기본 문제를 Prim algorithm 으로 풀어본 코드이다.

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

using namespace std;
typedef long long ll;

struct N {
	int node;
	ll val;
};

bool operator < (N a, N b) {
	return a.val < b.val;
}
bool operator > (N a, N b) {
	return a.val > b.val;
}
bool operator <= (N a, N b) {
	return a.val <= b.val;
}
bool operator >= (N a, N b) {
	return a.val >= b.val;
}
bool operator == (N a, N b) {
	return a.val == b.val;
}

priority_queue<N, vector<N>, greater<N>> q;
vector<vector<N>> adj;
vector<bool> visit;
ll answer = 0;
int v, e;

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

	adj.resize(v + 1);
	visit.assign(v + 1, false);

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

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

	int cur = 1; // start vertex == 1

	for (int i = 0; i < v - 1; i++) {
		visit[cur] = true;

		for (N x : adj[cur]) q.push({ x.node, x.val });
		
		while (visit[q.top().node]) q.pop(); // 방문 안 한 연결된 정점들 중 최소 가중치 선택
		answer += q.top().val;
		cur = q.top().node;
		q.pop();
	}

	cout << ::answer;
}

---

  정리 

  최소 스패닝 트리의 형태는 문제의 그래프에 대해서 항상 한 방법만 존재하지 않는다. 한 방법만 존재하는 그래프도 있겠지만, 보통 많은 정점과 간선들을 가지고 있는 그래프라면 많은 스패닝 트리의 형태를 가질 수 있을 것 이다. 이 알고리즘을 통해 구현될 수 있는 최소 스패닝 트리들 중 하나를 구현한다.

 

<최소 스패닝 트리의 특징 정리>

1. 최소 스패닝 트리의 간선의 수는 정점의 수 (V) - 1 개 이다.

2. 크루스칼 알고리즘은, 진행하면서 여러 트리가 생성이 되고 이 트리들이 합쳐지면서 최종적으로 하나의 최소 스패닝 트리가 구현이 된다.

3. 프림 알고리즘은 처음에 임의의 정점을 시작 정점으로 하고, 트리를 확장시켜 나가면서 최종적으로 하나의 최소 스패닝 트리를 구현한다.