크루스칼(Kruskal)
최소 신장 트리(MST: Minimum Spanning Tree)
- 신장 트리(Spanning Tree)
- 신장 트리는 그래프의 모든 정점이 간선으로 연결되어있고, 사이클이 없는 그래프를 말한다.
- 최소 신장 트리(MST: Minimum Spanning Tree)
- 최소 신장 트리는 그래프의 가능한 신장 트리들 중 비용의 합 최소인 신장 트리를 말한다.
- 최소 신장 트리를 구할 수 있는 알고리즘으로는 크루스칼, 프림 알고리즘이 있다.
크루스칼(Kruscal)
- 크루스칼은 그래프의 간선들을 하나씩 연결하면서 최소 신장 트리를 완성해나가는 알고리즘이다.
- 연결할 간선을 선택함에 있어서 그리디한 방법을 사용한다.
- 간선의 수가 적을 때 효율적인 알고리즘이다.
- 시간 복잡도는 O(ElogE)이다.
- 구현을 위해 Union-Find가 사용된다. 현재 글에서는 Union-Find에 대해서는 자세히 다루지 않을 것이므로, 필요한 경우 Union-Find를 설명한 게시글을 참조하자.
구현 방법
- 그래프의 모든 간선을 비용 오름차순으로 정렬한다.
- 정렬된 순서대로 간선을 선택하면서, 간선으로 연결된 정점들을 Union한다.
- 주의할 점은 간선으로 연결될 두 정점이 이미 같은 집합에 속해있다면, 해당 간선은 선택하지 않는다. 해당 간선을 연결할 경우 사이클이 발생하기 때문이다.
크루스칼(Kruscal) 예시 코드
/**
* 첫째 줄에 정점, 간선의 수가 주어진다.
* 두번째 줄부터 간선 정보가 주어진다.
* 6 9
* 1 6 5
* 2 4 6
* 1 2 7
* 3 5 15
* 5 6 9
* 3 4 10
* 1 3 11
* 2 3 3
* 4 5 7
*
* 최소 비용을 출력한다.
* 28
*/
public class Kruskal {
static int v;
static int e;
static int[] parents;
static PriorityQueue<Edge> pq;
static int result;
static class Edge implements Comparable<Edge> {
int from;
int to;
int cost;
public Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// 정점, 간선 개수 입력
st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
// 부모를 저장할 메모리
parents = makeSet(v);
// 간선 정보 저장
// 비용 오름차순 정렬
pq = new PriorityQueue<>();
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
pq.offer(new Edge(from, to, cost));
}
kruskal();
}
private static void kruskal() {
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int fromSet = find(edge.from);
int toSet = find(edge.to);
// 연결될 두 정점이 이미 같은 집합에 속해있다면, 간선을 선택하지 않는다.
if (fromSet == toSet) {
continue;
}
System.out.println("<선택된 간선의 정보>");
System.out.printf("from:%d to:%d cost:%d\n", edge.from, edge.to, edge.cost);
union(edge.from, edge.to);
result += edge.cost;
System.out.println("<현재 정점들의 부모>");
System.out.println(Arrays.toString(parents) + "\n");
}
System.out.printf("최소 비용: %d", result);
}
private static int[] makeSet(int size) {
// 1번 원소가 1번 인덱스에 대응할 수 있도록 배열 크기를 선언
int[] parents = new int[size + 1];
// 각 원소는 자기 자신을 가르킨다.
for (int i = 1; i < parents.length; i++) {
parents[i] = i;
}
return parents;
}
private static void union(int a, int b) {
int aRep = find(a); // a가 속한 집합의 대표
int bRep = find(b); // b가 속한 집합의 대표
if (aRep > bRep) {
parents[aRep] = bRep;
} else {
parents[bRep] = aRep;
}
}
private static int find(int x) {
if (parents[x] == x) {
return x;
} else {
return find(parents[x]);
}
}
}
/////////////////////////////////////////////////////////////////////////////////////////////
<선택된 간선의 정보>
from:2 to:3 cost:3
<현재 정점들의 부모>
[0, 1, 2, 2, 4, 5, 6]
<선택된 간선의 정보>
from:1 to:6 cost:5
<현재 정점들의 부모>
[0, 1, 2, 2, 4, 5, 1]
<선택된 간선의 정보>
from:2 to:4 cost:6
<현재 정점들의 부모>
[0, 1, 2, 2, 2, 5, 1]
<선택된 간선의 정보>
from:4 to:5 cost:7
<현재 정점들의 부모>
[0, 1, 2, 2, 2, 2, 1]
<선택된 간선의 정보>
from:1 to:2 cost:7
<현재 정점들의 부모>
[0, 1, 1, 2, 2, 2, 1]
최소 비용: 28