[ 그래프 MST ] 크루스칼 알고리즘

신장 트리 : 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리. 신장 트리는 여러가지. 

 

최소 신장 트리 : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리. 최소 신장 트리도 여러가지 나올 수 있다. 

특징 : 무방향 가중치 그래프, 사이클을 포함해서는 안된다. N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용해야 한다. 

 

크루스칼 알고리즘 

간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 

1. 모든 간선을 가중치에 따라 오름차순 정렬

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

- 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다.

3. n-1개의 간선이 선택될때까지 2를 반복. 

 

* 슈도 코드 

 

MST-KRUSKAL(G,w)
	A <- 0 // 0 : 공집합 
    For vertex v in G.V // G.V : 그래프의 정점 집합 
     	Make_Set(v) // G.E : 그래프의 간선 집합 
        
    G.E에 포함된 간선들을 가중치 w에 의해 정렬
    
    For 가중치가 가장 낮은 간선 G.E와 연결된 (u,v)선택 (n-1)개
    	If Find_Set(u) != Find_Set(v)
        A <- A 합 {(u,v)}
        Union(u,v);
        
    RETURN A

 

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class 크루스칼 {

	static int[] p; // 부모를 저장할 배열

	public static void main(String[] args) {
		Scanner sc = new Scanner(input);

		int V = sc.nextInt(); // 정점의 개수 0부터 시작한다.
		int E = sc.nextInt(); // 간선의 수

		// 간선배열을 만들어서 저장 (사용자 정의 클래스 / 2차원 배열)
		// [0]:시작정점 [1]:끝정점 [2]:가중치)
		int[][] edges = new int[E][3];

		for (int i = 0; i < E; i++) {
			edges[i][0] = sc.nextInt();
			edges[i][1] = sc.nextInt();
			edges[i][2] = sc.nextInt();
		} // 입력끝

		// 크루스칼 1단계 : 간선을 정렬(오름차순)
		Arrays.sort(edges, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});

		// 크루스칼 2단계 : 사이클이 발생안하도록 V-1개의 간선을 뽑는다.
		p = new int[V];
		// 2-1. make-set
		for (int i = 0; i < V; i++) {
			makeset(i);
		}

		// 2-2. 검사하면서 뽑기.
		int ans = 0; // 최소비용을 저장할 변수.
		int pick = 0; // 뽑은 간선의 수를 저장할 변수.

		// while을 쓰면 edges 배열을 돌릴 index 변수가 하나 필요.
		// for문을 이용해서 쓰면 if문을 통해 break를 걸어줘야한다.(선택)
		for (int i = 0; i < E; i++) {
			int px = findset(edges[i][0]);
			int py = findset(edges[i][1]);

			if (px != py) { // 사이클이 형성 안되는 경우. 
				union(x, y);
				union(px, py);
				ans += edges[i][2];
				pick++;
			}
			if (pick == V - 1)
				break;
		}
		System.out.println(ans);
	}

	static void union(int x, int y) {
		p[findset(y)] = findset(x); 
	}

	static int findset(int x) {
		// pass compression 적용. 
		if (x != p[x])
			p[x] = findset(p[x]);
		return p[x];
	}

	static void makeset(int i) {
		p[i] = i;
	}

	static String input = "7 11\r\n" + "0 1 32\r\n" + "0 2 31\r\n" + "0 5 60\r\n" + "0 6 51\r\n" + "1 2 21\r\n"
			+ "2 4 46\r\n" + "2 6 25\r\n" + "3 4 34\r\n" + "3 5 18\r\n" + "4 5 40\r\n" + "4 6 51\r\n" + "\r\n";
}