Kruskal 알고리즘 (MST)

 크루스칼 알고리즘은 간선을 하나씩 선택해서 MST를 찾는 알고리즘이다.

 

이때, 모든 간선을 가중치에 따라서 오름차순으로 정렬을 하고,

 

가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.

 

물론 사이클이 존재하면 안되기 때문에 사이클이 될 경우는 건너뛰고 다음으로 가중치가 낮은 간선을 선택한다.\

 

이를 간선이 n-1개 선택될 때까지 반복하게 된다.

 

Kruskal's algorithm - Wikipedia

 

위와 같이 정렬한 뒤 정점에 대한 간선을 가중치에 따라 선택한 경우다.

 

이를 코드로 작성해보자.

 

우선 2차원 배열을 만드는데, 정점의 개수 만큼의 행을 만들고, 3개의 열을 만든다.

 

0번째 열은 시작 정점

 

1번째 열은 끝 정점

 

2번째 열은 가중치를 저장할 것이다.

 

int v;
int e;

int edges[][]= new int [e][3];
//0 시작 정점, 1 끝 정점, 2 가중치

 

입력이 되었다 치고 가장 처음으로 간선을 정렬한다.

 

이때 가중치로 정렬을 해야한다.

 

Arrays.sort(edges, new Comparator<int[]>(){
	@Override
    public int compare(int [] o1, int []o2){
    	return o1[2]-o2[2];
    }
});

 

정렬 함수를 사용할 경우, 2차원 배열 내에 저장되어 있는 가중치를 비교해야 하기 때문에 조금 조정을 해준다.

 

다음으로는 V-1개의 간선을 뽑는데, 사이클이 아닌 경우만 뽑는다.

 

int p= new int[v];

findset(int x){
	if(x!=p[x])
		p[x]=findset(p[x]);
    return p[x];
}
//path compression 적용, 모든 노드의 부모 노드는 루트 노드로 변경

union(int x,int y){
	p[findset(y)]=findset(x);
} //합집합으로 합함




//make-set(자신을 대표 원소로 초기화)
for(int i=0;i<v;i++){
	p[i]=i;
}

int result=0; //최소 비용 저장 변수

int cnt= 0; //뽑은 간선의 수

for(int i=0;i<e;i++){
	int x= edges[i][0];// 시작 정점
    int y= edges[i][1];// 끝 정점
    
    if(findset(x)!=findset(y)){ //만약 두 정점이 같은 집합이 아닌 경우, 즉 사이클이 아닌 경우
    	union(x,y); //합집합으로 만들고
        result+=edges[i][2]; //해당 간선의 가중치를 추가
        cnt++; //뽑은 간선 수 추가
    }
    if(cnt==(v-1)) break; //간선이 정점을 모두 연결할 때 탈출
}

 

 

이런 식으로 진행할 수 있겠다.

 

이전에 공부했던 find set, union, make set 등을 활용해 크루스칼 알고리즘에 적용하는 것이다.

 

라고 이해했다.