Kruskal Algorithm
Kruskal Algorithm
개념
- 최소 비용 신장 트리를 찾는 알고리즘이다.
- 사이클을 형성하지 않는 그래프를 가리켜 신장 트리라고 한다.
- 신장 트리는 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.
- 신장 트리는 그래프 내에서 사이클을 형성하지 않는다.
- 신장 트리의 모든 간선의 가중치 합이 최소인 그래프를 가리켜 최소 비용 신장 트리(Minimum cost Spanning Tree), 또는 최소 신장 트리(MST, Minimum Spanning Tree)라고 한다.
- 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.
- 변의 개수 E(간선), 꼭짓점의 개수 V(노드)라고 하면 이 알고리즘은 $O(ElogV)$의 시간복잡도를 가진다.
- E(간선) : 거리, 비용에 해당되며 선에 해당되는 부분이다.
- V(노드) : 정점, 도시에 해당되며 동그라미에 해당되는 부분이다.
- ex. 최소의 비용으로 모든 섬이 통행 가능하도록 / 컴퓨터와 컴퓨터 사이를 모두 연결하는 최소비용(네트워크)
수행과정
- 주어진 무방향 그래프 $G = (V, E)$가 있을 때 크루스칼 알고리즘의 수행과정
- 그래프 G의 모든 간선들을 오름차순으로 정렬해서 가장 가중치가 작은 간선을 선택한다.
- 남은 간선들 중에 가장 가중치가 작은 간선을 찾은 후, 이 간선을 추가해도 사이클이 생기지 않는다면 이 간선을 선택한다.
- 선택된 간선들의 개수가 $n - 1$이 될 때까지 단계 2 과정을 반복한다.
-
크루스칼 알고리즘을 수행하기 위한 최초의 상태이다.
-
$E[][]$배열은 위 인접행렬의 가중치를 오름차순으로 정렬한 것으로 배열안에 들어가는 값은 해당 간선의 정점이다.
-
$S[]$배열은 각 정점이 속해있는 서브 트리이다. 크루스칼 알고리즘은 간선을 선택하기 때문에 여러개의 서브 트리가 생길 수 있다. 이 S배열을 이용해서 각 정점이 속해있는 서브트리를 확인하면서 사이클이 발생하는지를 검색한다. 현재는 각각이 다른 서브트리를 구성하고 있다.
-
$T[]$배열은 선택된 간선을 기억하는 배열이다.
-
가중치가 가장 적은 (4, 5)간선을 선택한다.
-
$E[][]$배열의 첫 번째 열의 값이 가장 작은 가중치를 가지고 있는 간선이다.
-
$S[]$배열의 4, 5 인덱스 값을 4로 변경해준다. 이는 정점 4, 5가 같은 서브 트리에 속해졌음을 뜻한다. 4로 변경한 이유는 여기서 사용하는 알고리즘은 작은 서브트리의 번호로 통합하는 방법을 사용하기 때문이다.
-
$T[]$배열에는 선택된 (4, 5)간선을 넣어준다.
-
그 다음으로 가중치가 적은 (3, 4)간선을 선택해준다
-
$E[][]$배열의 두 번째 열의 값이 가장 작은 가중치를 가지고 있는 간선이다.
-
$S[]$배열의 3, 4, 5 인덱스의 값을 3으로 변경해준다. 이는 정점 3, 4, 5가 같은 서브트리에 속해졌음을 뜻한다.
-
$T[]$배열에는선택된 (3, 4)간선을 넣어준다.
-
그 다음으로 가중치가 적은 (3, 5)간선을 선택해준다. 하지만 사이클이 발생하여 그냥 다음으로 넘어간다.
-
$E[][]$배열의 세 번째 열의 값이 가장 작은 가중치를 가지고 있는 간선이다.
-
$S[]$배열의 3, 5 인덱스의 값이 3으로 같아 같은 서브트리에 속해 있음을 알 수 있다. 이는 사이클이 형성됨을 검사하는 과정이다.
-
그 다음으로 가중치가 적은 (1, 2)간선을 선택해준다.
-
$E[][]$배열의 네 번쨰 열의 값이 가장 작은 가중치를 가지고 있는 간선이다.
-
$S[]$배열의 1, 2인덱스의 값을 1로 변경해준다. 이는 정점 1, 2가 같은 서브 트리에 속해졌음을 뜻한다.
-
$T[]$배열에는 선택된 (1, 2)간선을 넣어준다.
-
그 다음으로 가중치가 적은 (1, 3)간선을 선택해준다.
-
$E[][]$배열의 다섯번째 열의 값이 가장 작은 가중치를 가지고 있는 간선이다.
-
$S[]$배열의 1 ~ 5인덱스의 값을 1로 변경해준다. 이는 정점 1 ~ 5가 같은 서브 트리에 속해졌음을 뜻한다.
-
$T[]$배열에는 선택된 (1, 3)간선을 넣어준다.
-
그 다음으로 가중치가 적은 (2, 3)간선을 선택해준다. 하지만 사이클이 발생하여 그냥 다음으로 넘어간다.
-
$E[][]$배열의 여섯번째 열의 값이 가장 작은 가중치를 가지고 있는 간선이다.
-
$S[]$배열의 2, 3인덱스의 값이 1로 같아 같은 서브트리에 속해 있음을 알 수 있다. 이는 사이클이 형성됨을 검사하는 과정이다.
-
그 다음으로 가중치가 적은 (1, 6)간선을 선택해 준다.
-
$E[][]$배열의 일곱번째 열의 값이 가장 작은 가중치를 가지고 있는 간선이다.
-
$S[]$배열의 1 ~ 6인덱스의 값을 1로 변경해준다. 이는 정점 1 ~ 6이 같은 서브 트리에 속해졌음을 뜻한다.
-
$T[]$배열에는 선택된 (1, 6)간선을 넣어준다.
-
위에 과정을 거치면 n - 1번 수행하여 n - 1개의 간선이 선택되어 크루스칼 알고리즘은 종료되게 된다. 그리고 위 그림의 결과가 크루스칼의 알고리즘으로 구한 최소 비용 신장 트리이다.
코드
// 크루스칼 알고리즘을 이용하자 (https://kingpodo.tistory.com/51)
// 최소 비용 신장 트리 문제를 해결하기 위한 알고리즘
// 간선을 선택하기 떄문에 사이클 배제 과정이 필요하다!
public static int solution(int n, int[][] costs) {
int answer = 0;
int[][] costList = new int[n][n];
int minCost = costs[0][2];
int minIslandFrom = costs[0][0];
int minIslandTo = costs[0][1];
List<Boolean> visited = new ArrayList<>();
for (int i = 0; i < n; ++i)
visited.add(false);
for (int i = 0; i < costs.length; ++i) {
costList[costs[i][0]][costs[i][1]] = costs[i][2];
costList[costs[i][1]][costs[i][0]] = costs[i][2];
// 크루스칼 알고리즘의 출발 지점을 찾기 위한 과정
if (costs[i][2] < minCost) {
minCost = costs[i][2];
minIslandFrom = costs[i][0];
minIslandTo = costs[i][1];
}
}
while (visited.contains(false)) {
answer += minCost;
visited.set(minIslandFrom, true);
visited.set(minIslandTo, true);
minCost = (int)1e9; // 그냥 존재할리 없는 큰 수로 설정하기 위해 (1*10^9)
for (int i = 0; i < n; ++i) {
if (visited.get(i) == true) {
for (int j = 0; j < n; ++j) {
if (costList[i][j] != 0 && visited.get(j) == false && minCost > costList[i][j]) {
minCost = costList[i][j];
minIslandFrom = i;
minIslandTo = j;
}
}
}
}
}
return answer;
}