최소 신장 트리
최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.
최소 신장 트리의 특징
- 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 수는 항상 N - 1개다.
최소 신장 트리 핵심 이론
1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기
최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다. edge class는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다. 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화한다. 배열의 인덱스를 해당 자리의 값으로 초기화하면 된다.
2. 그래프 데이터를 가중치 기준으로 정렬하기
에지 리스트의 담긴 그래프를 데이터를 가중치 기준으로 오름차순 정렬한다.
3. 가중치가 낮은 에지부터 연결 시도하기
가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다. 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union연산을 이용해 두 노드를 연결한다.
4. 과정 3 반복하기
전체 노드의 개수가 N개이면 연결한 에지의 개수가 N - 1이 될 때까지 과정 3을 반복한다.
5. 총 에지 비용 출력하기
에지의 개수가 N - 1이 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력한다. 최소 신장 트리는 다른 그래프 알고리즘과 달리, 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있다. 그 이유는 에지를 기준으로 하는 알고리즘이기 때문이다. 또한 사이클이 존재하면 안 되는 특징을 지니고 있기 때문에 사이클 판별 알고리즘인 유니온 파인드 알고리즘을 내부에 구현해야 된다.
코드로 표현
static int[] parent;
static PriorityQueue<pEdge> que;
노드 수, 에지 수 입력
que = new PriorityQueue<>(); // 자동 정렬을 위해 우선순위 큐 자료구조 선택하기
parent = new int[n + 1];
parent배열 인덱스로 초기화
for(int i = 0; i < M; i++) {
시작 노드 s, 끝 노드 e, 가중치 입력받기 v
que.add(new pEdge(s,e, v));
}
int useEdge = 0;
int result = 0;
while(useEdge < N - 1) {
pEdge now = que.poll();
if(find(now.s) != find(now.e)) { // 같은 부모가 아니라면 연결해도 사이클이 생기지 않음
union(now.s, now.e);
result = result + now.v;
useEdge++;
}
}
Union 연산 : 대표 노드끼리 연결하기
a = find(a);
b = find(b);
if(a != b) {
parent[b] = a;
}
Find 연산
if(a == parent[a]) {
return a;
}
else {
return parent[a] = find(parent[a]); // 경로압축
}
class pEdge implements Comparable<pEdge> {
int s;
int e;
int v;
pEdge(int s, int e, int v) {
this.s = s;
this.e = e;
this.v = v;
}
@Override
public int compareTo(pEdge o) {
// 가중치를 기준으로 오름차순 정렬을 하기 위해 compareTo 재정의하기
return this.v - o.v;
}
}