MST (Minimun Spanning Tree, 최소 신장 트리)

그래프와 트리

• 비선형 자료구조 : 객체간의 관계를 관리하며 하나의 자료 뒤에 여러 개의 자료가 존재
• 그래프 : 노드(정점, 위치), 간선(위치간 관계), 가중치(간선에 할당된 비용)로 이루어진 자료구조
  • 유향 그래프, 무향 그래프 : 단방향이면 유향, 양방향이면 무향
• 트리 : 사이클 없이 모든 노드가 하나의 연결 요소인 그래프
  • 사이클 - 단순 경로(노드가 중복되지 않은 경로)의 시작점과 종점이 동일한 그래프
  • → 노드의 개수가 n개일 때, 간선의 개수는 n-1개 이다.
  • 기본 트리는 루트를 고려하지 않음, 루트를 고려하면 루티드 트리가 된다.

---

신장 트리(Spanning Tree) : 그래프 내의 모든 정점을 포함하는 트리

→ 최소 연결(간선의 수가 가장 적은 부분 그래프)

→ n개의 노드에 n-1개의 간선으로 모두 연결된 그래프

→ 하나의 그래프에 여러 개의 신장 트리가 존재한다.

→ “최소의 링크로 통신 네트워크 구축하기” 같은 예가 있을 수 있다

---

최소 신장 트리(Minimum Spanning Tree)

→ 그래프에서 Spanning Tree 중 가중치의 합이 최소인 트리

→ 가장 적은 수의 간선과 가중치의 합이 최소인 트리

즉, 가중치가 있는 연결된 그래프를 가중치의 합이 가장 작은 간선들로 구성된 트리로 만듦

---

크루스칼 알고리즘 (최소 신장 트리를 구하기 위한 그리디한 알고리즘)

• 사이클이 생기지 않고, 간선의 개수가 n-1개가 되도록 한다.
• 이때, 연결 요소들끼리 “연결되어 있는지, 연결 요소를 합치기”에서 Union-Find 알고리즘을 사용한다.

기본 개념

1. 가중치별로 간선들을 오름차순으로 정렬한다.
2. 연결 요소가 다를 때 연결 후, 가중치를 합한다.
3. 연결 요소가 같은 루트를 가질 때는(사이클 생성) 무시한다.

기본 예제 - MST

• 주어진 그래프에서 간선을 지워 트리를 만들어 최소 가중치 합을 출력하는 문제
• 입력 예제4 51 4 4
  1 3 4
  2 3 3
  1 2 2
  4 2 1

설계 및 구현

• 사이클이 생기지 않고 간선의 개수가 n-1개 되도록 한다.
• 가중치를 기준으로 정렬하고 연결 요소가 다를 때 연결하고 가중치를 합한다(유니온-파인드)
• c, a, b의 pair 처리 및 저장 (가중치, 노드, 노드)
  • vector<pair<int, pair<int, int>>> v;

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<pair<int, pair<int, int>>> v;
int par[10010];

int find(int x){
	if(par[x] == x) return x;
	else
		return par[x] = find(par[x]);
}

void union_(int a, int b)
{
	a = find(a);
	b = find(b);
	
	par[a] = b;
}

int main(){
	int a, b, c;
	
	cin >> n >> m;
	for(int i=0; i<m; i++){
		cin >> a >> b >> c;
		v.push_back({c, {a, b}});
	}
	sort(v.begin(), v.end());
	
	for(int i=0; i<n; i++)
		par[i] = i;
	
	long long answer = 0;
	
	for(int i=0; i<v.size(); i++)
	{
		a = find(v[i].second.first);
		b = find(v[i].second.second);
		c = v[i].first;
		
		if(a == b)
			continue;
		union_(a, b);
		answer += c;
	}
	cout << answer << endl;
}

 

예시 문제