Java - 크루스칼 알고리즘(Kruskal)

◎최소 스패닝 트리(minimum spanning tree)

 

출처: https://www.weeklyps.com/entry/%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Kruskals-algorithm

스패닝 트리(spannig tree)란 신장 트리라고도 하며, 그래프 내의 모든 정점을 사이클 없이 포함하는 트리를 말한다.

하나의 그래프는 여러 개의 스패닝 트리를 가질 수 있으며, 사이클이 생기면 안 되므로 N개의 노드에 대하여 정확하게 N-1개의 엣지(간선)를 가진다.

 

최소 스패닝 트리(minimum spanning tree)란 MST라고도 하며, 그래프가 가질 수 있는 스패닝 트리중 간선의 가중치 합이 가장 작은 트리를 말한다. 스패닝 트리 또한 하나에 그래프에 여러 개일 수 있다.

 

 

---

◎크루스칼 알고리즘(Kruskal)

 

크루스칼 알고리즘은 간선을 중점으로 그리디하게 최소 스패닝 트리를 찾는 알고리즘이다.

 

1. 간선의 가중치 값을 기반으로 오름차순 정렬한다.

2. 가중치 값이 낮은 간선부터 선택한다.

3. 선택한 간선의 두 정점이 연결되어 있지 않으면(사이클을 생성하지 않으면), 두 정점을 연결한다.

   선택한 간선의 두 정점이 연결되어 있으면(사이클을 생성하면), 다음 간선으로 넘어간다.

출처: https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

 

두 정점이 연결되어있는지 아닌지를 파악하기 위해서, 두 정점을 잇기 위해서는 Union-Find 알고리즘을 이용한다.

-유니온 파인드란?

https://kkwong-guin.tistory.com/60

Java - 유니온 파인드(Union-find)

---

◎크루스칼 알고리즘(Kruskal)의 구현

 

구현된 유니온 파인드 중에 Weighted Union Find을 사용하여 크루스칼 알고리즘을 구현하였다

 

-Weighted Union Find

Weighted Union Find

package MST;
 
public class WeightedUnionFind {
	// 각 집합의 루트 노드(최소값)을 나타내는 parent 배열
	public int[] parent;
 
	// size = 요소의 개수
	WeightedUnionFind(int size) {
		this.parent = new int[size];
 
		// 초기 상태의 모든 집합의 요소 개수는 1
		for (int i = 0; i < size; i++) {
			parent[i] = -1;
		}
	}
 
	// 입력된 요소의 루트 노드 반환
	private int getParent(int x) {
 
		// x가 루트 요소이면, x반환
		if (parent[x] < 0)
			return x;
 
		/*
		 * x 가 루트 노드가 아니라면 x부모의 루트 노트를 재귀적으로 찾음.
		 */
		return parent[x] = getParent(parent[x]);
 
	}
 
	// 입력된 요소가 같은 집합에 속하는지 알려줌
	public boolean find(int x, int y) {
		x = getParent(x);
		y = getParent(y);
 
		if (x == y)
			return true;
 
		return false;
	}
 
	// 입력된 요소들이 속한 집합을 병합
	public void union(int x, int y) {
		x = getParent(x);
		y = getParent(y);
 
		// 각 집합의 루트 노드가 같으면 같은 집합임
		if (x == y) {
			return;
		}
 
		// 작은 트리가 큰 트리 밑에 들어가게 병합
		// parent[x], parent[y] 값은 음수이므로 값이 작은 경우가 더 높이가 큰 노드이다.
		if (parent[x] < parent[y]) {
			parent[x] += parent[y];
			parent[y] = x;
		} else {
			parent[y] += parent[x];
			parent[x] = y;
		}
	}
}

 

코드 구현:

 

1. 힙으로 [노드1,노드2,비용]으로 이루어진 이차원 배열인 costs를 비용을 기준으로 오름차순 정렬

ex. [0,1,2]이면, 0번 노드와 1번 노드의 간선 가중치의 값이 2라는 것이다.

 

2. 힙이 빌 때까지 요소를 꺼내고 꺼내진 요소가

사이클을 형성하면(=두 정점이 연결되어 있으면 ,같은 트리에 속하면 , find() 값이 true), 병합(union) 하지 않고.

사이클을 형성하지 않으면 (=두 정점이 연결되어 있지 않으면 ,같은 트리에 속하지 않으면 , find() 값이 false),

병합(union)한다.

package MST;

import java.util.Comparator;
import java.util.PriorityQueue;

import MST.WeightedUnionFind;

public class Kruskal_algorithm {
	
	int nodes; //노드 개수
	int[][] costs; // [노드1,노드2,비용]으로 이루어진 이차원배열
	WeightedUnionFind wuf;
	
	public Kruskal_algorithm(int nodes, int[][] costs) {
		this.nodes = nodes;
		this.costs = costs;
		 wuf = new WeightedUnionFind(this.nodes);
	}
	
	public int solution() {
		
		int answer = 0;
		
		//비용 값을 기준으로 최소 힙 구현 
        PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] a, int[] b) {
				// TODO Auto-generated method stub
				return a[2] - b[2];
						
			}
        	
        });
        
        for(int[] value : costs) {
        	heap.add(value);
        }
        
      //힙이 빌때까지(모든 간선 값을 볼때까지) 반복
        while(!heap.isEmpty()) {
        	int[] tmp = heap.poll();
        	if(!wuf.find(tmp[0],tmp[1])) {
        		wuf.union(tmp[0],tmp[1]);
        		answer = answer + tmp[2];
        	}
        }
		
		return answer;
	}
	
	public static void main(String[] args) {
    	
    	int[][] costs = {{0,2,1},{1,2,2},{2,3,2},{0,4,2},{2,4,2}} ;
    	Kruskal_algorithm sol = new Kruskal_algorithm(5,costs);
    	System.out.println(sol.solution());
    	
    }
}

실행결과:

7

 

빨간색 간선 = 연결된 간선

흑색 간선 = 연결되지 않은 간선

최소 스패닝 트리는 위와 같으므로 1+2+2+2 = 7이다.

---

◎크루스칼 알고리즘(Kruskal)의 효율성

크루스칼 알고리즘은 간선을 중점으로 MST를 찾으므로, 그래프 내에 간선의 수가 적은 희소 그래프(Sparse Graph)일 경우에 적합이다.

프림 알고리즘은 노드를 중점으로 MST를 찾으므로, 그래프 내에 간선이 많이 존재하는 밀집 그래프(Dense Graph)일 경우에 적합하다.

 

프림 알고리즘

https://kkwong-guin.tistory.com/62

Java - 프림 알고리즘(Prim)

---

Github codes

https://github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/MST

jerry-ryu/java_problemsolving_algorithm