최소 신장트리 알고리즘, 크루스칼 알고리즘 (Kruskal)
- Algorithm/Concept
- 2021. 12. 15.
신장트리
신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다.
최소 신장트리
최소한의 비용으로 구성되는 신장 트리다.
1) 23 + 13 = 36
2) 23 + 25 = 48
3) 25 + 13 = 38
이 경우, 1)번의 경우가 가장 최소한의 비용으로 연결되므로 최소 신장 트리라고 할 수 있다.
크루스칼 알고리즘 (Kruskal)
최소 신장 트리를 찾는 알고리즘 중 대표적인 알고리즘이 '크루스칼 알고리즘'이다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있는데 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 먼저 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다.
간선이 사이클을 발생시키는지 확인한다.
1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
크루스칼 알고리즘 동작원리
크루스칼 알고리즘의 동작원리를 코드와 함께 이해해보자.
들어가기전, 서로소 집합 포스팅 바로가기
https://devfunny.tistory.com/659
서로소 집합 (Disjoint Sets) 알고리즘
서로소 집합 (Disjoint Sets) 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조는 두 종류의 연산을 지원한다. 1) 합집합 (Union) 두개의 원소가 포함된 집합을 하나의 집합으로 합친다. 2)
devfunny.tistory.com
서로소 집합 코드와 거의 비슷하다. 입력받은 데이터를 변수에 셋팅하는 과정도 눈여겨보자.
package Y20_Graph;
import java.util.*;
public class Kruskal {
public static int v; // 노드의 개수(V)
public static int e; // 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
// 모든 간선을 담을 리스트
public static ArrayList<Edge> edges = new ArrayList<>();
// 최종 비용을 담을 변수
public static int result = 0;
// 특정 원소가 속한 집합을 찾기
public static int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) {
return x;
}
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) {
parent[b] = a;
} else {
parent[a] = b;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// 모든 간선에 대한 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
edges.add(new Edge(cost, a, b));
}
...
}
}
class Edge implements Comparable<Edge> {
private int distance;
private int nodeA;
private int nodeB;
public Edge(int distance, int nodeA, int nodeB) {
this.distance = distance;
this.nodeA = nodeA;
this.nodeB = nodeB;
}
public int getDistance() {
return this.distance;
}
public int getNodeA() {
return this.nodeA;
}
public int getNodeB() {
return this.nodeB;
}
// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
@Override
public int compareTo(Edge other) {
if (this.distance < other.distance) {
return -1;
}
return 1;
}
}
1) 그래프의 모든 간성 정보만 빼내어 오름차순 정렬을 한다.
- 오름차순 정렬
...
public static void main(String[] args) {
...
// 간선을 비용순으로 정렬
Collections.sort(edges);
...
}
...
2) 가장 짧은 간선인 (3, 4)를 선택한다. 아직 처리하지 않았으므로 진행한다.
여기서, 사이클의 발생 여부를 체크해야한다.
...
public static void main(String[] args) {
...
// 간선을 비용순으로 정렬
Collections.sort(edges);
// 간선을 하나씩 확인하며
for (Edge edge : edges) {
int cost = edge.getDistance();
int a = edge.getNodeA();
int b = edge.getNodeB();
// 사이클이 발생하지 않는 경우에만 집합에 포함
if (findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
}
}
System.out.println(result);
}
...
3) 아직 처리되지 않은 간선 중에서 가장 짧은 간선인 (4, 7)을 선택한다.
4) 아직 처리되지 않은 간선 중에서 가장 짧은 간선인 (4, 6)을 선택한다.
5) 아직 처리되지 않은 간선 중에서 가장 짧은 간선인 (6, 7)을 선택한다.
6) 아직 처리되지 않은 간선 중에서 가장 짧은 간선인 (1, 2)을 선택한다.
7) 아직 처리되지 않은 간선 중에서 가장 짧은 간선인 (2, 6)을 선택한다.
8) 아직 처리되지 않은 간선 중에서 가장 짧은 간선인 (2, 3)을 선택한다.
9) 아직 처리되지 않은 간선 중에서 가장 짧은 간선인 (5, 6)을 선택한다.
10) 아직 처리되지 않은 간선 중에서 가장 짧은 간선인 (1, 5)을 선택한다.
11) 마지막으로 최소 신장 트리에 포함되어있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당한다.
전체 코드
package Y20_Graph;
import java.util.*;
public class Kruskal {
public static int v; // 노드의 개수(V)
public static int e; // 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
// 모든 간선을 담을 리스트
public static ArrayList<Edge> edges = new ArrayList<>();
// 최종 비용을 담을 변수
public static int result = 0;
// 특정 원소가 속한 집합을 찾기
public static int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) {
return x;
}
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) {
parent[b] = a;
} else {
parent[a] = b;
}
}
/*
7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// 모든 간선에 대한 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
edges.add(new Edge(cost, a, b));
}
// 간선을 비용순으로 정렬
Collections.sort(edges);
// 간선을 하나씩 확인하며
for (Edge edge : edges) {
int cost = edge.getDistance();
int a = edge.getNodeA();
int b = edge.getNodeB();
// 사이클이 발생하지 않는 경우에만 집합에 포함
if (findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
}
}
System.out.println(result);
}
}
class Edge implements Comparable<Edge> {
private int distance;
private int nodeA;
private int nodeB;
public Edge(int distance, int nodeA, int nodeB) {
this.distance = distance;
this.nodeA = nodeA;
this.nodeB = nodeB;
}
public int getDistance() {
return this.distance;
}
public int getNodeA() {
return this.nodeA;
}
public int getNodeB() {
return this.nodeB;
}
// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
@Override
public int compareTo(Edge other) {
if (this.distance < other.distance) {
return -1;
}
return 1;
}
}
결국 결과 코드를 도출하는 코드는, 사이클이 발생하지 않을때마다 결과 result 변수를 총 합으로 갱신하여 출력한다.
'이것이 코딩테스트다' 교재 참고
'Algorithm > Concept' 카테고리의 다른 글
| binarySearch 이진탐색의 lowerBound, upperBound (중복 원소 중 첫번째 인덱스와 마지막 인덱스 구하기) (0) | 2021.12.26 |
|---|---|
| 위상 정렬 (Topology Sort) 알고리즘 (0) | 2021.12.15 |
| 서로소 집합 (Disjoint Sets) 알고리즘 (0) | 2021.12.15 |
| 최단경로 찾기 - 플로이드 워셜 알고리즘 (0) | 2021.12.08 |
| 우선순위 큐 (Priority Queue) (0) | 2021.12.03 |