Kruskal algorithm

1. Problem

- 크루스칼 알고리즘을 사용하여 모든 노드를 연결하는 최소 비용을 구해보자.

- 최소 비용 신장 트리(minimum cost spanning tree)를 만드는 대표적인 알고리즘이다.

- 각 노드를 연결하는 간선의 정보(연결된 노드, 비용)를 이용해 간선을 정렬한 후 사이클을 만들지 않게 적은 비용의 간선부터 차례대로 선택해 나간다.

- 최소한의 비용으로 모든 노드를 이어야 하기 때문에, 사이클을 만드는 것은 비용 낭비가 된다.

- 간선을 선택하기 전에 사이클 테이블을 확인해야 하는데, 이는 이미 연결된 노드인지 알아보기 위함이다. 사이클 테이블은 union-find(합집합 찾기) 알고리즘을 이용한다.

 

2. Input

1) int[][] graph

- 연결된 노드를 표현

2) int[] cost

- cost[i] == graph[i]의 비용

 

3. Output

1) 모든 노드를 연결하는 최소 비용

 

4. Example

// 노드는 0번부터 6번까지 7개가 있고, 간선은 11개가 있다.
// 간선의 비용을 오름차순으로 정렬한다.	[5,7,10,11,15,17,25,28,40,44,50]
// 사이클 테이블도 만들어 놓는다.						   parent = [0,1,2,3,4,5,6]
// 간선의 비용이 작은것부터 확인한다. 사이클 테이블을 보고 부모가 같지 않으면 해당 간선을 선택한다.
// 비용이 5인 간선: parent[2]==2 != parent[6]==6
			-> MST= 2 - 6,				cost = 5,  parent = [0,1,2,3,4,5,2]
// 비용이 7인 간선: parent[3]==3 != parent[6]==2
			-> MST= 2 - 6 - 3,			cost = 12, parent = [0,1,2,2,4,5,2]
// 비용이 10인 간선: parent[0]==0 != parent[1]==1
			-> MST= 0 - 1 / 2 - 6- 3,		cost = 22, parent = [0,0,2,2,4,5,2]
// 비용이 11인 간선: parent[1]==0 != parent[5]==5 
			-> MST = 0 - 1 - 5 / 2 - 6- 3,		cost = 33, parent = [0,0,2,2,4,0,2]
// 비용이 15인 간선: parent[3]==2 != parent[4]==4
			-> MST = 0 - 1 - 5 / 2 - 6 - 3 - 4,	cost = 48, parent = [0,0,2,2,2,0,2]
// 비용이 17인 간선: parent[0]==0 == parent[5]==0 -> skip
// 비용이 25인 간선: parent[1]==0 != parent[2]==2 
			-> MST = 0 - 1 - (5) - 2 - 6 - 3 - 4,	cost = 73, parent = [0,0,0,0,0,0,0]
// 사이클 테이블의 값이 모두 같아졌으므로 종료한다.
// 모든 노드를 잇는 최소 비용은 73이다.

 

5. Code

static int[] parent = new int[7]; // 클래스 변수로 선언

// main()
// 7개의 노드와 11개의 간선에 대한 그래프를 2차원 배열로 표현
// graph[i][j]: i번과 j번을 연결하는 모든 간선들의 정보
// cost[i] == graph[i]의 비용
int[][] graph = {{2,6},{3,6},{0,1},{1,5},{3,4},{0,5},{1,2},{0,4},{1,4},{5,6},{2,3}};
int[] cost = {5,7,10,11,15,17,25,28,40,44,50}; // 편의상 오름차순으로 정렬시킴

for(int i=0 ; i<7 ; i++) // 각 노드에 대해 자기 값을 초기 부모로 지정한다
    parent[i] = i;
int min = 0; // 최소 비용
for(int i=0 ; i<graph.length ; i++) {  // 그래프의 간선을 따라가며 부모를 합친다.
    if(!find(graph[i][0],graph[i][1])) { // 부모가 같지 않을 경우에만 선택해서
        min += cost[i];
        union(graph[i][0], graph[i][1]); // 합친다.
    }
}

// 합치는 과정
static void union(int a, int b) {
    a = getParent(a); // 두 노드의 부모를 찾은 후
    b = getParent(b);
    if(a<b) parent[b] = a; // 더 작은 수를 부모로 한다.
    else parent[a] = b;
}

static int getParent(int a) { // 해당 노드의 부모를 찾아 반환한다.
    if(parent[a]!=a)                       // 간선의 정보가 업데이트 될 때
        parent[a] = getParent(parent[a]);  // 부모가 달라질 수 있으므로
    return parent[a];                      // 재귀호출을 이용해 최종 부모를 찾는다.
}
    
static boolean find(int a, int b) { // 부모가 같으면 true를 반환한다.
    return getParent(a)==getParent(b);
}

// main()
System.out.println(min); // 73

- 모든 간선을 다 돌게 해놨지만, 모든 노드를 방문했을 때 또는 parent의 값이 모두 같아지게 됐을 때 등의 break 조건을 걸어둘 수도 있다.