Spanning Tree
Spanning Tree는 그래프 내 모든 정점을 포함하는 Tree를 말한다. 모든 정점을 연결하는 Path를 만드는 경우 사용되는 개념으로 N개의 정점이 존재할 경우 간선은 항상 N-1개이다.(Cycle 존재 X)
Minimum Spanning Tree
MST는 최소 신장 트리를 말하며 모든 edge의 weight 합이 최소인 트리를 말한다.
구현 방법에는 Kruskal 알고리즘과 Prim 알고리즘이 있다.
Kruskal Algorithm
Kruskal은 Greedy 알고리즘을 기반으로 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 알고리즘이다. 각 간선을 선택하는 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.
[방식]
1. 그래프들의 간선을 가중치 오름차순 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택
3. 해당 간선을 MST 집합에 추가
[구현 방법]
1. union&find 선언 (unf 배열, union 함수, find 함수 선언)
2. Edge class( node1, node2, cost : node1과 node2를 잇는 간선의 비용이 cost) 선언
2. 비용기준 오름차순 정렬
3. for문(edge) -> find(v1), find(v2) 비교
4. 같지 않을 경우(disjoint set인 경우, 즉 사이클 x) union수행
Prim Algorithm
Prim은 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장하는 알고리즘이다. 정점 선택을 기반으로 이전 단계에서 만들어진 신장트리를 확장하는 방식으로 이루어진다.
[방식]
1. 시작단계 - 시작정점을 MST에 포함
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택. 트리 확장 ( 가장 낮은 가중치 선택)
3. 트리가 N-1개의 간선을 가질 때까지 반복
[구현 방법]
1. Edge class( node1, cost : node1로 가는 간선의 비용이 cost) 선언
1. 각 정점의 이웃 간선 정보를 담는 ArrayList 선언
2. 정점들의 ArrayList를 담는 ArrayList인 graph 선언
3. 지나간 정점인지 체크하는 ch 배열 선언
4. PriorityQueue 선언 (비용이 최소인 간선 부터 빼는 queue)
5. 시작 정점 정보 add
6. while(!pq.isEmpty())
하나씩 빼면서 해당 정점의 ch값 확인
0인 경우 -> 1로 바꾸고 해당 정점의 이웃 간선 정보 add
참고
