크루스칼 알고리즘

최소 비용 신장트리를 만들기 위한 알고리즘.

가작 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.

1. 간선의 가중치 순서에 맞게 정렬한다.

2. 사이클이 형성되어 있는지 확인한다.

3. 사이클이 형성되어 있지 않으면 간선을 가중치가 작은 순서대로 그래프에 포함시킨다.

그래프의 간선에 가중치가 있을때 최단 경로를 찾는 문제에서 사용된다.

 

 

public class Main{
	public static class Edge implements Comparable<Edge>{
		int node[] = new int[2];
		int weight;
		
		Edge() {}
		Edge(int a, int b, int weight) {
			this.node[0] = a;
			this.node[1] = b;
			this.weight = weight;
		}
		
		@Override
		public int compareTo(Edge e) {
			return Integer.compare(this.weight, e.weight);
		}
	}
	// 부모노드 찾기
	public static int getParent(int arr[], int x) {
		if(arr[x] == x) 
			return x;
		return arr[x] = getParent(arr, arr[x]);
	}
	// 두 부모 노드 합치기
	public static void unionParent(int arr[], int a, int b) {
		a = getParent(arr, a);
		b = getParent(arr, b);
		if(a < b) {
			arr[b] = a;
		}else {
			arr[a] = b;
		}
	}
	
	// 같은 부모를 가지는지 확인, 노드가 연결되어있는지 확인
	public static boolean findParent(int arr[], int a, int b) {
		a = getParent(arr, a);
		b = getParent(arr, b);
		if(a == b)
			return true;
		else
			return false;
	}
    public static void main(String[] args) throws Exception {
    	Scanner sc = new Scanner(System.in);
    	int arr[] = {0, 1, 2, 3, 4, 5, 6}; // 부모 배열
    	int n = 6;	// 노드 갯수
    	int m = 9;	// 간선 갯수
    	ArrayList<Edge> edgeList = new ArrayList<Edge>();
    	
    	// 노드 추가
    	edgeList.add(new Edge(1, 2, 10));
    	edgeList.add(new Edge(1, 3, 2));
    	edgeList.add(new Edge(2, 3, 20));
    	edgeList.add(new Edge(2, 4, 30));
    	edgeList.add(new Edge(3, 4, 5));
    	edgeList.add(new Edge(3, 5, 16));
    	edgeList.add(new Edge(3, 6, 15));
    	edgeList.add(new Edge(4, 6, 40));
    	edgeList.add(new Edge(5, 6, 42));
    	
    	// 가중치가 작은 순서대로 정렬
    	Collections.sort(edgeList);
    	System.out.println("가중치 정렬");
    	for(int i=0; i<edgeList.size(); i++) {
    		System.out.print(edgeList.get(i).weight + " ");
    	}
    	System.out.println();
    	
    	int sum = 0;
    	System.out.println("그래프 연결");
    	for(int i=0; i<edgeList.size(); i++) {
    		// 사이클이 발생하지 않는 경우 그래프에 포함
    		if(!findParent(arr, edgeList.get(i).node[0], edgeList.get(i).node[1])) {
    			sum += edgeList.get(i).weight;
    			unionParent(arr, edgeList.get(i).node[0], edgeList.get(i).node[1]);
    			System.out.println(edgeList.get(i).node[0] + " " + edgeList.get(i).node[1]);
    		}
    	}
    	
    	System.out.println("가중치 합");
    	System.out.println(sum);
    }
}
============================================================================================
가중치 정렬
2 5 10 15 16 20 30 40 42 
그래프 연결
1 3
3 4
1 2
3 6
3 5
가중치 합
48