[최소신장트리] Kruskal

크루스칼 알고리즘은 대표적인 최소신장트리 알고리즘 중 하나이다.

간선을 하나씩 선택해서 MST(최소신장트리)를 찾는 알고리즘이다.

 

1) 최초로 모든 간선을 가중치에 따라 오름차순으로 정렬한 뒤,

2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. 이때, 사이클이 존재하면 다음으로 가중치가 낮은 간선을 택한다.

3) 간선이 모두 선택될 때 까지 2를 반복한다.

 

지난번 포스팅에서 다뤘던 Union-Find 알고리즘을 응용해서 만드는데, 

새로운 자료형을 선언해 주는 것이 편하기 때문에 Edge라는 자료형을 만들어주었다.

간선이 어디에서 와서 어디로 가는지, 가중치가 얼마인지에 대한 정보가 담겨있다.

static class Edge implements Comparable<Edge>{
		int from,to,weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.weight, o.weight);
		}
	}

 

make, findSet, union 함수는 union-find 와 동일하게 사용한다.

static void make() {
		//자신의 인덱스랑 같은 번호를 넣어줌. 즉, 자기 자신이 각 집합의 root.
		for(int i=0; i<V; i++) {
			parents[i] = i; 
		}
	}
	
	static int findSet(int a) {
		//만약 내가 대표자면 나 리턴
		if(parents[a] == a) return a;
		//아니라면 내 자리에 root의 값을 넣어줌.
		return parents[a] = findSet(parents[a]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot) //둘이 같다면 이미 같은 집합에 속해있는 것
			return false;
		//다르다면 A밑에 B붙임.
		parents[bRoot] = aRoot;
		return true;
	}

그 이후, kruskal 의 핵심 부분은 이 부분이다. 

사이클이 발생하는지 아닌지 확인해주는 부분이다. 

edgeList 는 Edge의 배열로, 간선들의 정보가 담겨있다. 

이 배열에서 하나씩 돌아보며 출발지와 목적지가 연결되어있을 경우 넘어가주고, 연결되어있지 않다면 연결해준다. 

	int result = 0; //가중치의 합
	int count = 0; //간선 선택 개수
		
	for(Edge edge: edgeList) {
		if(union(edge.from, edge.to)) { //union 성공하면 다른 집합.
			result += edge.weight;
			if(++count == V-1) break;
		}
	}
	System.out.println(result);

이렇게 연결해주면 가장 작은 가중치로 모두 연결된  거리를 구할 수 있다.