신장 트리란 ?
-> 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 생성되지 않는 부분 그래프
-> 즉 모든 노드들을 연결 하면서도 사이클이 생성되지 않는 그래프를 의미한다.
-> 이는 다리를 놓으면서 최소한으로 모든 섬들을 연결하는 문제로 생각할 수 있다.
: 따라서 최소 신장 트리는 N개의 정점을 (N-1)개의 간선으로 연결하게 된다.
MST의 구현 방법
1. Kruskal MST Algorithm
- Greedy Method/Algorithm을 이용하여 그래프의 모든 정점을 최소비용으로 연결하는 알고리즘이다.
- 각 사이클에서 최소 비용의 간선을 택하는데 사이클을 이루지 않도록 한다.
- 간선을 선택하면서 이루어지는 알고리즘이다.
- 가장 작은 비용을 가진 간선들만 선택하기 때문에 Greedy Algorithm이라고 할 수 있다.
1. 그래프의 간선들을 가중치로 오름차순 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
3. 정답에 추가한다.
2. Prim MST Algorithm
-시작 정점에서부터 시작하여 신장트리를 단계적으로 확장해나가는 방법이다.
1. 시작 정점을 답에 추가한다.
2. 인접한 정점 중에서 최소 간선으로 연결된 정점을 선택하여 확장
3. 트리가 N-1개의 간선을 가질 때 까지 반복한다.