: 최소한의 연결을 가지면서 모든 정점을 포함하고, 가중치도 최소인 것
특징
- 스패닝 트리 중 간선 가중치 합이 최소
- 스패닝 트리이므로 n-1개의 간선
- 간선의 weight(가중치) 합이 최소여야 한다.
- Cycle이 없어야 한다.
스패닝 트리? 최소한의 연결로 모든 정점을 포함하는 트리
- n개의 정점을 가지는 그래프의 간선의 수는 n-1개
- 전체 그래프에서 일부 간선을 선택해 만든 트리
사용 사례
: 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 하는 곳
- 도로 건설: 최소 도로 길이로 도시들을 모두 연결
- 전기 회로: 최소 전선 길이로 단자들을 모두 연결
- 통신: 최소 전화선으로 케이블 망 구성
크루스칼
: 전체에서 가중치가 작은 간선부터 연결 (그리디 알고리즘)해 MST를 만드는 알고리즘
- 각 단계에서 Cycle을 이루지 않는 최소 비용 간선 선택
- 부모노드 병합하고, 사이클 확인하는 과정에서 보통 union-find 사용
과정
- 가중치를 기준으로 간선을 오름차순 정렬
- 가중치 낮은 것부터, 사이클을 만들지 않는 간선을 선택해 MST 집합에 추가
프림
: 하나의 시작점을 잡고 연결된 정점들 중 가중치 낮고, 사이클을 만들지 않는 간선 선택
- 크루스칼과는 다르게 정점을 기준으로 선택
- 이전 단계에서 만들어 놓은 MST를 확장하는 방법으로 사용되기도 함
과정
- 시작 정점 선택 - 이 정점을 포함한 집합은 MST가 된다.
- 앞 단계에서 만들어진 MST에 인접한 정점 중 낮은 가중치로 연결된 정점
- 이 때 사이클을 만들지 않도록
- n-1 간선을 가질 때까지 반복
Reference)
https://www.crocus.co.kr/733
https://github.com/WeareSoft/tech-interview/blob/master/contents/algorithm.md