[자료구조] 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘은 노드들이 서로 간선을 통해서 연결되어 있을때 각 노드들을 모두 방문할수있는 최소경로를 구하는

알고리즘이다.

 

크루스칼 알고리즘은 탐욕 알고리즘으로 문제를 해결해나갈수 있다.

매번 경로를 선택할때마다 최단 경로를 선택해서 나아가기 때문이다.

(그렇다고 탐욕 알고리즘이 최적의 해를 항상 구해주는것은 아니다.)

 

그럼 이제 크루스칼 알고리즘의 특징부터 확인해보자.

 

크루스칼 알고리즘의 특징

1. 간선(경로)의 개수는 항상 노드 - 1 이다.

2. 간선을 선택할때 사이클이 형성되어선 안된다.

왼 : 사이클 아닌것 오 : 사이클 인것

이제 특징을 알아봤으니 크루스칼 알고리즘의 동작원리를 확인해보자.

 

크루스칼 알고리즘의 동작원리

 

크루스칼 알고리즘의 기본적인 동작 원리는 아래와 같다.

1. 경로가 제일 작은 순으로 선택을 한다.

2. 경로를 선택할때 선택한 경로로 인해 사이클이 생긴다면 해당 경로는 선택하지 않는다.

 

 

 

자 그럼 위의 순서대로 일단은 먼저 해보자.

 

1. 경로가 제일 작은 순으로 선택을 한다.

 

경로가 제일 작은순으로 선택을 하려면 일단 아래와 같은 2차원 배열이 있어야 한다.

 

[[시작,끝,경로비용], [시작,끝,경로비용], [시작,끝,경로비용], [시작,끝,경로비용]]

 

위처럼 배열이 주어졌을때 우리는 경로비용을 기준으로 위의 2차원 배열을 정렬하면 된다.

 

예제를 통해서 보자.

int[][] costs = {{0, 1, 5}, {1, 2, 3}, {2, 3, 3}, {3, 1, 2}, {3, 0, 4}, {2, 4, 6}, {4, 0, 7}};

 

위와 같은 변수와 배열이 주어졌을때 우리는 이제 아래와 같이 경로비용을 기준으로 정렬을 해준다.

Arrays.sort(costs,(o1,o2)->(o1[2]-o2[2]));

결과 

[[3, 1, 2], [1, 2, 3], [2, 3, 3], [3, 0, 4], [0, 1, 5], [2, 4, 6], [4, 0, 7]]

 

그럼 이제 경로비용을 기준으로 오름차순 정렬을 완료 했으니 다음 단계로 넘어가자.

 

 

 

 

 

2. 경로를 선택할때 선택한 경로로 인해 사이클이 생긴다면 해당 경로는 선택하지 않는다.

 

아마 이부분이 무슨 소리인지 이해가 되지 않을수도 있다.

해당 내용은 무슨 소리냐면 이미 갈수 있는 경로라면 굳이 또 추가하지 않아도 되는소리이다.

 

예를 들어서 

0 - 1 경로를 방문한다 했을때 우리는 해당 경로를 통해서 0과 1 모두 방문 할수 있게 됐다.

그 상황에서 우리가 새로운 1- 2 경로를 간다고 하면 우리는 이제 0,1,2 를 모두 방문할수 있게 된다.

하지만 위의 상황에서 0 - 2 경로가 있다고 했을때 우리는 이미 0,1,2를 모두 방문할수 있는 시점에서  0 - 2 를 선택할 이유가 없는것이다.

 

그래서 사이클을 선택하지 않는것인대 우리는 이런 원리를 Union Find 알고리즘을 통해서 

항상 부모노드의 값을 따라서 바꾸는 원리를 구현했다.

 

연결하려는 노드 값들의 부모 노드값이 같다면 이미 방문이 가능한것이기에

경로는 피하는것이다.

 

※Union Find 알고리즘을 모르시는 분들은 아래링크 참조

https://wpioneer.tistory.com/113

[자료구조] Union Find 알고리즘 : 재귀호출 (Java)

 

 

그럼 이제 위의 1번과 2번 과정을 통해서 크루스칼 알고리즘을 구현하는것을 그림으로 살펴보자.

 

for문으로 costs[][]에 접근해 최소 비용 cost를 구한다고 보자

 

 

index = 0

parents[3]과 parents[1] 부모 노드 비교 -> 다르니 큰쪽의 노드가 부모노드 변경

 

변경후 cost  += 2

 

 

 

---

 

index = 1

parents[1]과 parents[2] 부모 노드 비교 -> 다르니 큰쪽의 노드가 부모노드 변경

변경후 cost  += 3

 

 

 

---

 

 

index = 2

parents[2]와 parents[3] 부모 노드 비교 -> 같으니 다음 index로 이동

 

 

---

 

index = 3

 

parents[3]과 parents[0] 부모 노드 비교 -> 다르니 큰쪽의 노드가 부모노드 변경

※3을 바꾸지 않고 1의 부모노드를 바꾸지 않은 이유는 3에서 부모노드 1로 접근해서 값을 변경했기 때문

 

cost += 4

 

 

---

 

index = 4

parents[0]과 parents[1] 부모 노드 비교 -> 같으니 다음 index로 이동

 

 

---

 

 

index = 5

parents[2]와 parents[4] 부모 노드 비교 -> 다르니 큰쪽의 노드가 부모노드 변경

※위도 마찬가지로 1이 아닌 0으로 바뀌는 이유는 2의 부모노드인 1의 부모노드의 값인 0으로 접근했기 때문

 

cost += 6

 

 

---

 

 

index = 6

parents[4]와 parents[0] 부모 노드 비교 -> 같으니 다음 index로 이동

 

---

 

index = 7

반복문 탈출

 

그리고 나서 cost return

 

그래서 최종적으로 cost는 2+3+4+6 으로 15가 답이 된다.

 

위의 그림을 소스로 표현하자면 아래와 같다.

 

 

main 함수

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		
		int n = 5; //노드 개수
		int[][] costs = {{0, 1, 5}, {1, 2, 3}, {2, 3, 3}, {3, 1, 2}, {3, 0, 4}, {2, 4, 6}, {4, 0, 7}};
		
		Arrays.sort(costs,(o1,o2)->(o1[2]-o2[2]));
		
		int[] parent = new int[n];
		for(int i = 0; i<n;i++) {
			parent[i] = i;
		}
		
        Kruskal kru = new Kruskal();
        int mst = kru.giveMst(costs, parent);
        
        System.out.println("최소비용 : "+ mst);
		
//		System.out.println(p.solution(n, costs));


	}

 

Kruskal 클래스

public class Kruskal {
	
	public int giveMst(int[][] costs, int[] parent) {
		int mst = 0;
		
		UnionFind uf = new UnionFind();
		System.out.println(Arrays.deepToString(costs));
		//여기서 할것은 costs에 있는 간선들이 서로 연결되어 있는지 확인하고 아니라면 
		for(int i = 0; i<costs.length;i++) {
			int x = costs[i][0];
			int y = costs[i][1];
			int cost = costs[i][2];
			if(uf.checkLine(x,y,parent)) { //간선이 연결되어 있는지 확인
				System.out.println(x+" - "+y+ " 존재!!");
				continue;
			}else {
				System.out.println(x+" - "+y+ " 연결!!");
				uf.union(x, y, parent);
				System.out.println("부모 노드 : " +Arrays.toString(parent));
				mst+=cost;
			}
		}
		
		return mst;
	}
	
}

 

Union Find 클래스

public class UnionFind {
	//일단은 노드를 연결해주는 부분이 있어야 한다.
	public void union(int x, int y, int[] parent) {
		x = find(x, parent); //2의 부모는 0
		y = find(y, parent); //4의 부모는 4
		
		if(x<y) {
			//x와 y의 부모노드값이 서로 다르면 같아지게 이어줘야 한다.
			//이어주는 부분에서 주의해야 할점은 노드들을 오름차순으로 정렬후에 먼저 받는 x의 값이 y값보다 작아야 한다.
			parent[y] = x;
		}else {
			parent[x] = y;
		}
	}

	public boolean checkLine(int x, int y, int[] parent) {
		// TODO Auto-generated method stub
		
		int getX = find(x,parent);
		int getY = find(y,parent);
	
		return getX==getY;
	}
	
	//여기선 부모 노드의 값을 리턴해주면 된다.
	public int find(int x, int[] parent) {
		// TODO Auto-generated method stub
		//주의해야할점은 부모 노드의 값과 전달 받은 값이 상이 하다면 해당 부모의 노드를 다시 받아와야 한다.
		if(x == parent[x]) {
			return x;
		}else { 
			//내 노드와 받은 노드의 값이 다르다면 부모 노드에 다른 값이 들어갔다는건데 그 값의 부모노드를 알기위해선 
			//parent[x] 안에 있는 값의 부모노드값을 받아와야 한다. 
			return find(parent[x],parent);
		}
	}	
}