[알고리즘] 최소 스패닝 트리 (Minimum Spanning Tree) & 크루스칼 알고리즘

최소 스패닝 트리란?

연결된 트리가 있을 때, 최소 개수 & 최소 비용을 가진 edge를 선택하여 모든 vertex가 연결된 트리를 만들고,

그것을 최소 스패닝 트리라고 부른다.
위의 그림에서 edge를 1개 이상 선택하여 부분 트리를 만들 수 있다. 그러나 그 중에서 모든 vertex가 연결되면서 비용이 최소가 되야 한다.

모든 vertex가 연결되면서 최소 비용이 되기 위해서는 vertex N개를 선택하기 위해서 edge는 N-1을 선택하는 것이 최소가 될 것이다.

크루스칼 알고리즘

최소 스패닝 트리를 구하는 알고리즘에는 크게 크루스칼 알고리즘과 프림 알고리즘이 있다.

그 중에서 크루스칼 알고리즘이 구현이 조금 더 쉬운 편이라서 해당 알고리즘을 자주 활용하는 편이다.

해당 알고리즘을 설명 후 구현까지 해보겠다.

크루스칼 알고리즘은 Edge 기반 선택 알고리즘이라고도 부른다.

1. 간선들을 오름차순으로 '정렬' 한다
2. 가장 낮은 가중치의 간선을 선택한다. 해당 간선을 선택할 경우 사이클이 생기면 제외한다.
3. 해당 간선을 최소 스패닝 트리(MST)에 포함한다.
4. 계속 반복하여 N-1개의 간선을 선택할때까지

시간 복잡도는 어떻게 될까?

1. 간선들을 오름차순으로 정렬 -> ElogE
2. 가장 낮은 가중치의 간선을 선택한다 -> logE (priority queue의 최소힙을 사용)
3. 이를 V-1개의 간선을 선택할때까지 -> 따라서 2번을 V번 하게 된다.

결국 시간 복잡도는 ElogE + VlogE 입니다. 그러나 보통 E > V 이므로, ElogE라고 할 수 있습니다 ><

구현을 해보자 !

• 분리집합 + priority queue를 통한 Min heap을 통해 구현할 수 있다.
• 사이클인지는 어떻게 확인할까? 
  이를 위해서는 분리 집합에 대해서 알아야 한다. 
• https://bboglebbogle.tistory.com/13?category=998282

[알고리즘] 분리집합 (Union Fnd)

해당 글을 통해 사이클 확인 방법을 배워 보세요, parent가 같을 경우 cycle 이라고 판단하면 된다.

 

int N; //정점의 개수
int p[N]; //분리집합 대표를 여기에다가 저장할 것임!

int getp(int n){
	if(p[n] == n) return n;
	return p[n] = getp(p[n]);
}

void Union(int x, int y){
	// getp(x);
	// getp(y);
	p[p[n]] = p[y]
}

priority_queue<pair<int, pair<int, int>>> pq;
// pq에는 간선들을 저장할 것이다. 간선의 가중치와 두 정점을 모두 저장하쟈

int selected = 0;
int total = 0;

while(selected < N - 1 && !pq.empty()){
		int c = -pq.top().first;
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		pq.pop();
		
		if(getp(x) != getp(y)){
				Union(x, y);
				selected += 1;
				total += c;
		}
}

if(selected != N - 1) cout << "불가능";
else cout << total;

🦔 풀어볼만한 백준 문제들

1197번 최소 스패닝 트리

1647번 도시 분할 계획

4386번 별자리 만들기

17472번 다리 만들기 2

2887번 행성 터널 

 

더 다양한 난이도의 문제들은 내가 잘 참고하고 있는 깃헙 문제집에서 확인해 보자.

https://github.com/tony9402/baekjoon/tree/main/minimum_spanning_tree

GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)