[Algorithm] 최소신장트리(MST) - Kruskal
간선을 하나씩 선택해서 MST를 찾는 알고리즘
- 최소, 모든 간선을 가중치에 따라 오름차순으로 정렬
- 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
- 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
- n-1개의 간선이 선택될 때 까지 2를 반복
code
Edge
public class Edge {
int adjvertex; // 간선의 다른쪽 끝 정점
int weight; // 간선의 가중치
public Edge(int v, int wt) {
adjvertex = v;
weight = wt;
}
}
KruskalMST
import java.util.*;
public class KruskalMST {
int N, M; // 그래프 정점, 간선의 수
List<Edge>[] graph;
UnionFind uf; // Union-Find 연산을 사용하기 위해
Edge[] tree;
static class Weight_Comparison implements Comparator<Edge> { //weight를 기준으로 우선순위큐를 사용하기 위해
public int compare(Edge e, Edge f) {
if(e.weight > f.weight)
return 1;
else if(e.weight < f.weight)
return -1;
return 0;
}
}
public KruskalMST(List<Edge>[] adjList, int numOfEdges) {
N = adjList.length;
M = numOfEdges;
graph = adjList;
uf = new UnionFind(N); // Union-Find 연산을 사용하기 위해
tree = new Edge[N-1];
}
public Edge[] mst() { // Kruskal 알고리즘
Weight_Comparison BY_WEIGHT = new Weight_Comparison(); // 우선순위큐를 weight 기준으로 구성하기 위해
PriorityQueue<Edge> pq = new PriorityQueue<Edge>(M, BY_WEIGHT); // 자바 라이브러리의 우선순위큐 사용
// 우선순위큐의 크기로 M(간선의 수)을 지정, BY_WEIGHT는 line 24의 comparator
for (int i = 0; i < N; i++){
for (Edge e : graph[i]){
pq.add(e); // edgeArray의 간선 객체들을 pq에 삽입
}
}
int count = 0;
while (!pq.isEmpty() && count < N-1) {
Edge e = pq.poll(); // 최소 가중치를 가진 간선를 pq에서 제거하고 가져옴
int u = e.vertex; // 가져온 간선의 한 쪽 정점
int v = e.adjvertex; // 가져온 간선의 다른 한 쪽 정점
if (!uf.isConnected(u, v)) { // v와 w가 각각 다른 집합에 속해 있으면
uf.union(u, v); // v가 속한 집합과 u가 속한 집합의 합집합 수행
tree[count++] = e; // e를 MST의 간선으로서 tree에 추가
}
}
return tree;
}
}
UnionFind
public class UnionFind {
protected int[] p; // 배열크기는 정점의 수 N이고 p[i]는 i의 부모 원소를 저장한다.
protected int[] rank;
public UnionFind(int N) {
p = new int[N];
rank = new int[N];
for (int i = 0; i < N; i++) {
p[i] = i; // 초기엔 N개의 트리가 각각 i 자기 자신이 부모이기 떄문에
rank[i] = 0; // 초기엔 N개의 트리 각각의 rank를 0으로 초기화
}
}
//i가 속한 집합의 루트노드를 재귀적으로 찾고 최종적으로 경로상의 각 원소의 부모를 루트노드로 만든다.
protected int find(int i) { // 경로 압축
if ( i != p[i])
p[i] = find(p[i]); //리턴하며 경로상의 각 노드의 부모가 루트가되도록 만든다.
return p[i];
}
//i와 j가 같은 트리에 있는지를 검사
public boolean isConnected(int i, int j) {
return find(i) == find(j);
}
public void union(int i, int j) { // Union 연산
int iroot = find(i);
int jroot = find(j);
if (iroot == jroot) return; // 루트노드가 동일하면 더이상의 수행없이 그대로 리턴
// rank가 높은 루트노드가 승자로 union을 수행한다.
if (rank[iroot] > rank[jroot])
p[jroot] = iroot; // iroot가 승자
else if (rank[iroot] < rank[jroot])
p[iroot] = jroot; // jroot가 승자
else {
p[jroot] = iroot; // 둘중에 하나 임의로 승자
rank[iroot]++; // iroot의 rank 1 증가
}
}
}
수행시간
간선을 정렬(또는 우선순위큐의 삽입과 삭제)하는데 소요되는 시간 $O(MlogM) = O(MlogN)$
신장트리가 만들어질 때까지 간선에 대해 isConnected()와 union()을 수행하는 시간 $O((M+N)logN)$
$$
O(MlogN) + O((M+N)logN) = O(MlogN)
$$
Reference
『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)
『SW 문제해결 응용 - 구현 - 그래프의 최소 비용 문제』
https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AV3GBeD6AF4BBARB#
'Algorithm' 카테고리의 다른 글
거품정렬(Bubble Sort) (0) | 2020.07.19 |
---|---|
[Algorithm] 최소신장트리(MST) (0) | 2019.11.10 |
[Algorithm] 최소신장트리(MST) - Prim (0) | 2019.11.10 |
PowerSet(부분집합) (0) | 2019.10.19 |
Disjoint-Set (서로소 집합) (0) | 2019.10.15 |