MST, 최소 신장 트리, 크루스칼 알고리즘

cost가 작은 최소 연결 트리

최소 연결 = 간선의 수가 가장 적다

 

DFS, BFS을 이용하여 신장 트리를 찾을 수 있다.

탐색 도중에 사용된 간선만 모으면 만들 수 있다.

n개의 정점을 연결함으로 (n-1)개 간선으로 연결함

 

Spanning Tree 사용 예시?

회사 내 모든 전화기를 가장 적은 수의 케이블을 이용하여 연결하는 경우

최소의 선으로 링크를 연결하는 경우 

 

 

MST 특징

 1.간선 Cost가 최소

 2. (N-1)개 간선

 3. 간선이 포함되면 안됨

 

쿠르스칼 알고리즘 : MST 구현방법

1. 간선 가중치를 오름차순 정렬

2. 부모를 본인 자신으로 하는 경우로 parent 배열 초기화

3. 싸이클이 존재하지 않는 경우 union find 알고리즘 적용(싸이클이 생기지 않는 경우)

 

이를 순서대로 sum하여 cost가 가장 작은 값을 만든다

 

 

----------------------------------------------------------------------------------------------------------------------------

상세 내용

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

 

 

관련 문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

문제풀이(답안)

https://github.com/huisoo/algo_test/blob/master/Min_spanning_tree_bak1197.java

huisoo/algo_test