최소 신장 트리(Minimum Spanning Tree )

= 최소 스패닝 트리 = MST

 

1. 최소 신장 트리란?

그래프에서 최소 비용으로 모든 구간을 연결하는 트리이다. (모든 정점을 최소 비용으로 연결) 

 

2. 최소 신장 트리의 특징

- MST는 트리이므로, Cycle이 존재하면 안된다. (Cycle 판별: 유니온 파인드 이용)

- 답은 여러 개가 될  수도 있다. 

 

3. 최소 신장 트리를 구하는 알고리즘 종류

 1. 크루스칼 알고리즘

 2. 프림 알고리즘 : 추후 공부할 예정 

 

4. 크루스칼 알고리즘

  - 시간복잡도: O(nlogn)

  - 원리 : 노드가 n개 일 때, n개의 노드를 전부 연결하려면 n-1개의 간선이 필요하다.

  - 구현 단계

    1. 가중치 값을 기준으로 오름차순 정렬

    2. 유니온 파인드 자료구조를 이용해 간선(연결선) 선택

      - for문을 돌려, 추가하려고 하는 간선에 대해 이미  두 해당 노드가 같은 그룹인지 아닌지 판단한다.

      - 같은 그룹이면, 이미 연결된 노드들이므로 그 간선은 추가X

      - 이렇게 1중 for문을 돌려서 간선이 n-1개 선택되면 for문을 종료한다.  

 

 

5. C++ 최소 신장 트리(크루스칼) 구현

#include <iostream>
using namespace std;

int main() {

	// 추후 추가 예정

	return 0;
}

 

 

 

---

백준 알고리즘 분류 [최소 스패닝 트리]

https://www.acmicpc.net/problemset?sort=ac_desc&algo=49

문제 - 1 페이지

 

백준 단계별 [최소 신장 트리]

https://www.acmicpc.net/step/15

최소 신장 트리 단계