최소 신장 트리 MST, Union-Find C++

개요

1. 그래프와 트리의 차이점

트리는 무방향 간선을 가지며 사이클이 없고 특정 노드 간 경로가 유일한 그래프다.

그래프 내에는 여러개의 신장 트리가 있을 수 있다.

 

2. 신장 트리 (Spanning tree)

N개의 노드를 N - 1개의 간선으로 모든 노드가 연결된 트리

 

3. 최소 신장 트리 MST

가중치가 최소인 신장 트리 = Minimum Spanning Tree

간선에 가중치가 주어졌을때 간선의 합이 최소인 Spanning Tree가 최소 신장 트리가 된다.

 

그래프 예시

 

아래와 같은 간선간 가중치가 있는 그래프가 있다고 가정 해보자

노드의 개수는 9개이므로 8개의 간선으로 9개의 노드를 모두 이을 수 있는 가중치의 최소값은 얼마일까?

 

각 가중치가 오른쪽과 같은 간선을 선택하여 더하면 20 + 21 + 1 + 13 + 17 + 6 + 15 + 3 = 96이 되면서 최소의 비용으로 모든 노드를 연결할 수 있는 Spanning Tree를 만들 수 있다.

 

1. 데이터를 저장한다. (노드A, 노드B, 간선의 가중치)
2. 노드를 정렬한다. (연결된 가중치를 기준)
3. 노드를 하나씩 연결해 보기 (Union-Find을 활용해 같은 그룹인지 여부 판별)

실습

코드

#include <iostream>
#include <algorithm>

using namespace std;

int parent[20];

struct Edge {
	int a, b, cost;
	bool operator<(Edge right) const {
		if (cost < right.cost) return true;
		if (cost > right.cost) return false;

		if (a < right.a) return true;
		if (a > right.a) return false;

		if (b < right.b) return true;
		if (b > right.b) return false;

		return false;
	}
};

Edge edges[20];

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

void Union(int a, int b) {
	int rootA = Find(a);
	int rootB = Find(b);

	if (rootA == rootB) return;
	parent[rootB] = rootA;
}

int main() {
	int n, e;
	cin >> n >> e;

	// 1. 데이터 저장
	for (int i = 0; i < e; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		edges[i] = { a, b, cost };
	}

	// 2. 데이터 정렬
	sort(edges, edges + e);

	// 3. 하나씩 연결해보기 (Union-Find을 활용해 같은 그룹인지 여부를 판별)
	// 3 - 1. parent 세팅
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	
	// 3 - 2. 하나씩 연결해보기
	int sum = 0;
	for (int i = 0; i < e; i++) {
		Edge edge = edges[i];
		if (Find(edge.a) == Find(edge.b)) continue;
		Union(edge.a, edge.b);
		sum += edge.cost;
	}
	cout << sum;
}

 

입력

9 13
1 2 1
2 3 13
3 4 17
1 6 21
3 5 82
5 4 99
4 8 6
5 6 20
5 7 57
4 7 15
8 9 31
6 7 32
7 9 3

 

출력

96