[도구정리] 최소 신장 트리(MST) - 크루스칼(kruskal) 알고리즘

최소 신장 트리(MST)란?

최소 신장 트리(Minimum Spanning Tree)를 알기 위해서는 신장 트리(Spanning Tree)가 무엇인지 알아야 한다.

 

신장 트리(Spanning Tree)

• 위의 그림 그래프에서 아래 그래프 3개 모두 신장 트리(위 그림에 따르면 3개가 더 존재함.)
• 그래프의 모든 정점을 포함하는 트리
• 그래프의 최소 연결 부분 그래프로 사이클이 없음
• 정점의 개수 n개면 간선의 개수 n-1개 가짐(사이클이 존재하지 않기 때문이다.)
• 하나의 그래프에 많은 신장 트리 존재

최소 신장 트리(Minimum Spanning Tree)

• 가운데 신장 트리는 신장 트리 중 가중치 합이 가장 최소인 최소 신장 트리
• 신장 트리 중 간선의 가중치 합이 최소인 트리
• 사이클이 없는 그래프 중 최소의 가중치

---

크루스칼(kruskal) 알고리즘

그래프에서 최소 신장 트리를 만드는 대표적인 알고리즘 2개가 있다. 그 중 하나인 크루스칼 알고리즘이다.

 

크루스칼(kruskal) 알고리즘이란?

• 간선을 하나씩 늘려감
• O(Elog V) 시간복잡도 가짐
• 탐욕법 사용

과정

초기 상태로 정점(=노드)는 서로 연결되어 있지 않다.

간선을 하나씩 고려하면서 MST를 만든다.

크루스칼 알고리즘을 수행하고 완성된 그래프는 최소 신장 트리이다.

간선을 추가하는 방식은 다음과 같다.

1) 크기가 가장 작은 간선부터 모든 간선을 살핀다. 이때 간선은 가중치에 대해 오름차순으로 정렬되어 있다.(우선순위 큐 혹은 정렬을 이용한다.)

2) 간선을 그래프에 포함 했을 때, MST에 사이클이 생기지 않으면 추가한다. 이 과정은 유니온 파인드 알고리즘을 이용하여 확인한다.

정점 v와 정점 w를 잇는 간선e가 있을 때, 정점 v와 정점 w가 같은 부모 노드를 가진다면 간선 e는 MST에 추가하지 않는다. → 사이클을 방지한다.

위와 같은 그림이 있다. 각 parent는 어떤 그룹에 연결되어있는지를 나타낸다.

간선에 대한 배열은 비용을 기준으로 오름차순 정렬되어있다.

 

1. (v, w, cost) = (1, 3, 3)

• find(1) = 1, find(3) = 3해당 간선을 채택한 뒤, union(1,3)을 수행하여 같은 그룹으로 묶는다.
• 각 노드의 부모가 다르다. 사이클이 생기지 않았다는 말이다.

2. (v, w, cost) = (1, 4, 8)

• find(1) = 1, find(4) = 4
• 위와 동일하게 간선을 채택하고 그룹으로 묶어준다.

3. (v, w, cost) = (4, 5, 9)

• find(4) = 1, find(5) = 5위의 parent 배열을 보면 헷갈릴 수 있는 부분이 parent[5]에 대하여 1이 아닌 4가 들어간 것이다. 이 부분은 union-find 알고리즘을 어떻게 설계하고 이용하느냐의 차이로 parent[5] = 1이 되어도 동일하다.
• 위와 동일하게 간선을 채택하고 그룹으로 묶어준다.

4. (v, w, cost) = (1, 2, 10)

• find(1) = 1, find(2) = 2
• 위와 동일하게 간선을 채택하고 그룹으로 묶어준다.

5. (v, w, cost) = (2, 3, 13)

• 여기서 parent[5] = 1이 된 것은 위와 설명한 동일한 이유이다. union-find를 어떤 방식으로 사용하느냐에 따라 4로 두어도 되고, 1로 두어도 된다.
• find(2) = 1, find(3) = 1
• 부모가 동일하다. 추가하는 경우 사이클이 생기게 된다는 것이다. 채택하지 않는다.

6. (v, w, cost) = (2, 5, 14)

• find(2) = 1, find(5) = 1
• 여기서 parent[5] = 4였어도 find(5)가 1이 나오게만 해주면 된다.
• 부모가 동일하므로 채택하지 않는다.

 

최종 완성

 

최종 코드

public class Main {
	// Union 연산 (작은 인덱스를 부모로 설정)
	public static void union(int[] parent, int x, int y) {
	    int rootX = find(parent, x);
	    int rootY = find(parent, y);
	    
	    if (rootX != rootY) {
	        if (rootX < rootY) {
	            parent[rootY] = rootX;
	        } else {
	            parent[rootX] = rootY;
	        }
	    }
	}
	
	// Find 연산 (경로 압축 포함)
	public static int find(int[] parent, int x) {
	    if (parent[x] != x) {
	        parent[x] = find(parent, parent[x]); // 경로 압축
	    }
	    return parent[x];
	}

	
    // 크루스칼
	public static void kruskal(int[][] graph, int[] parent) {
		int cost = 0;
		for(int i = 0; i < graph.length;i++) {
			if (find(parent, graph[i][0]) != find(parent, graph[i][1])) {
				cost += graph[i][2];
				union(parent, graph[i][0], graph[i][1]);
			}
		}
        
        // 최소 신장 트리의 총 가중치 출력
		System.out.println(cost);
	}
	
	public static void main(String[] args) throws IOException {
    	// 간선 입력 받기, 그래프에 저장
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());
		int[][] graph = new int[m][3];
		
		StringTokenizer st;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			graph[i][0] = Integer.parseInt(st.nextToken()); // 간선 나가는 정점
			graph[i][1] = Integer.parseInt(st.nextToken()); // 간선 들어오는 정점
			graph[i][2] = Integer.parseInt(st.nextToken()); // 가중치
		}
		
        // 간선 정렬
		Arrays.sort(graph, (o1, o2) -> o1[2] - o2[2]);
		
        // 부모노드 초기화
		int[] parent = new int[n + 1];
		for (int i = 0; i < parent.length; i++) {
			parent[i] = i;
		}
        
		//크루스칼 알고리즘 수행
		kruskal(graph, parent)
	}
}