Kruskal (크루스칼) 알고리즘

저번 Union Find에 이어서

Kruskal 알고리즘 정리하겠습니다.

 

목차

- 크루스칼 알고리즘 이란?
- 예제를 통해 크루스칼 이론 학습하기
- 코드로 구현하기

 

- 6줄 요약 -
크루스칼 알고리즘은 최소비용 신장트리를 만드는 알고리즘이다. 알고리즘은 다음과 같다.

1) 간선 가중치 중 가장 작은 값을 선택한다.
2) 간선을 연결하여 순환(Cycle)이 생기지 않는다면 연결 후 1)로 이동.
3) 연결 시 순환(Cycle)이 생기면 연결하지 않고 1)로 이동.
(순환이 여부는 Union Find 알고리즘을 활용하여 알아냅니다!)
최소비용 신장트리의 간선의 수는 "노드의 수 - 1" 

 

시작 합시다!

 

 

1. Kruskal 알고리즘이란?

Kruskal 알고리즘이란 모든 노드를 싸이클이 없도록 연결하는 트리를 만들기 위해 사용되는 알고리즘 입니다.

즉, 최소비용 신장트리를 찾는 알고리즘 이죠.

 

각 노드를 연결하는 간선에는 가중치가 있고, 해당 가중치 중 가장 적은 비용으로 모두 연결해야 할때 이 알고리즘을 사용합니다.

아래 예시를 보면서 이해를 해보져

그림 1. 크루스칼 알고리즘 예제

 

먼저 그림 1과 같이 5개의 노드가 있고, 연결 된 간선에는 가중치가 포함되어있을때,

크루스칼 알고리즘을 이용해서 가장 적은 비용으로 최소신장 트리를 만드는 방법을 알아보겠습니다.

 

크루스칼 알고리즘 적용 방식은 아래 3가지 입니다.

1) 간선 가중치 중 가장 작은 값을 선택한다.
2) 간선을 연결하여 순환(Cycle)이 생기지 않는다면 연결 후 1)로 이동.
3) 연결 시 순환(Cycle)이 생기면 연결하지 않고 1)로 이동.
(순환이 여부는 Union Find 알고리즘을 활용하여 알아냅니다!)

간단하죠?

그림 1 예제를 통해 진행하겠습니다.

 

 

 

2. 예제를 통해 크루스칼 이론 학습하기

그림 1 그래프를 최소 비용으로 연결한다면 아래 그림 2와 같이 연결 될 것 입니다. 

그림 2. 예상 결과 값

 

그럼 이렇게 연결이 되는지 확인해봅시다.

보기 편하도록 아래 그림 3과 같이 정리하고 시작할게요

그림 3. 최소비용 신장트리 만들기

 

 

최소비용 신장트리 만들기 시작!

2-1. 우선 첫번째로 가장 작은 가중치를 갖는 간선  '2<->5'를 선택 후 연결합니다.

그림 4. 최소비용 신장트리 만들기(1)

 

2-2. 이제 계속 반복 합니다. 다음 가장 작은 가중치 '4 <-> 5'를 선택하고 연결 합니다.

그림 5. 최소비용 신장트리 만들기(2)

 

2-3. 다음 작은 가중치 '1 <-> 3'을 선택하고 연결합니다.

그림 6. 최소비용 신장트리 만들기(3)

 

2-4 다음 작은 가중치 '2 <-> 4'를 선택합니다.

그런데! 2와 4를 연결하면 2 - 4 - 5 노드에 순환이 생기기 때문에 넘어가고 그 다음 작은 값 '1 <-> 2'를 선택 합니다.

그림 7. 최소비용 신장트리 만들기(4)

 

2-5 이제 어떤 간선을 선택해도 Cycle이 생성됩니다. 그렇기 때문에 최소비용 신장트리가 완성되었기에
종료!

그림 8. 최소비용 신장트리 만들기 (완성)

 

맨 처음 예상했던 결과값이랑 동일한 것을 확인할 수 있습니다.

그럼 바로 코드 구현으로 들어가 보져

 

 

 

3. 코드 구현하기

사실 크루스칼 알로리즘은

Union Find 알고리즘에  
 * 1. 간선의 최솟값을 찾기 => Arrays.sort (정렬 이용)
 * 2. 정렬된 배열 순서대로, 간선을 연결할 때 Cycle이 생기지 않으면 연결하도록 하기

를 추가하면 Kruskal 알고리즘이 됩니다.
(아래 예제는 최소 비용 신장트리의 간선의 합을 구하는 코드 입니다.)

	//부모 노드를 찾을 수 있는 함수
	public int getParent(int parent[],int x) {
		if(parent[x] == x) return x;
		return parent[x] = getParent(parent,parent[x]);
	}
	//노드 연결해서 부모 값 작은걸로 변경하기
	public int[] changeParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if(a<b) parent[b] = a;
		else parent[a] = b;
		
		return parent;
	}
	//부모 값이 동일한지 확인
	public boolean findParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a==b) return true;
		return false;
	}
	
	
	public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] parent = new int[n]; //1,2,3,4,5,6
        for(int i=0; i<n; i++) {parent[i] = i;}
        
        //간선 정렬
        Arrays.sort(costs, new Comparator<int[]>() {
			@Override
			public int compare(int[] arg0, int[] arg1) {
				//오름차순 정렬
				return arg0[2]-arg1[2];
			}
        });
        
        //간선 오름차순으로 정렬되었기 때문에 Cycle이 아니라면 하나씩 더해주면 됨.
        //0->1= 1 , 0->2 =2, 2->3 = 1 인경우 배열에 3의정보는 주지 않기때문에 costs.length 기준으로 하는것임
        for(int i=0; i<costs.length; i++) {
        	//Cycle이 아닌경우 간선 가중치 더하기
        	if(!findParent(parent,costs[i][0],costs[i][1])) {
        		//연결하기
        		System.out.print(costs[i][2]+" ");
        		answer += costs[i][2];
            	changeParent(parent,costs[i][0],costs[i][1]);
        	}
        }
        System.out.println();
        System.out.println(answer);
        
        return answer;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		island_connection ic = new island_connection();
		int n = 5;
		int[][] costs = {{0,1,3},{0,2,4},{0,3,9},{1,3,3},{1,4,1},{2,3,5},{3,4,2}};
		ic.solution(n, costs);
	}

 

실행하면 결과 값 : 10이 나오는 것을 확인할 수 있습니다.

 

이렇게 하면 Kruskal 알고리즘 정리 완료!