[JAVA] 최소 신장 트리 - Kruskal 알고리즘 <Minimum Spanning Tree - Kruskal>

최소 신장 트리 - MST(Minimum Spanning Tree)

최소 신장 트리란, 여러 스패닝 트리 중 간선들의 가중치의 총합이 가장 작은 트리를 이야기한다.

 

그렇다면 최소 신장 트리를 알려면 신장 트리(Spanning Tree)를 알아야 하는데, 스패닝 트리(신장 트리)란 모든 정점을 연결했을 때 간선의 수가 V - 1개이고 사이클이 존재 하지 않는 무방향 그래프를 의미한다.

 

신장 트리 예시

모든 정점이 연결되었고, 5개의 정점에 대해서 4개의 간선만을 가지고 있으며, 사이클이 존재하지 않는 무방향 그래프임을 볼 수 있다.

간선에 적혀있는 숫자들은 간선의 가중치를 의미한다.

 

최소 신장 트리

위 그림의 경우, 기존에 1번 정점과 3번 정점을 연결하는 가중치 3의 간선대신 2번 정점과 3번 정점을 연결하는 가중치 2의 간선을 선택해서 이 경우보다 가중치가 작은 간선을 선택하는 경우가 없다고 가정해보자.

 

위와 같은 상황이 바로 최소 신장 트리의 예시를 의미한다.

 

 

최소 신장 트리의 구현

최소 신장 트리는 이렇게 쉬운 개념을 가지고 있으며, 구현하는 방법은 2가지가 존재한다.

• Kruskal 알고리즘
• Prim 알고리즘

Kruskal 알고리즘

크루스칼 알고리즘의 경우 이전에 설명한 Union-Find 알고리즘을 활용해서 전개시킬 수 있다.

왜 유니온 파인드 알고리즘을 적용시킬까?
-> 유니온 파인드 알고리즘의 적용 예시 중 하나가 바로 사이클 판별인데, 최소 신장 트리의 조건인 무방향 그래프를 구현하기 위해서 유니온 파인드 알고리즘을 적용시키는 것.
-> 결국, 두 정점이 이미 같은 트리(집합)라면 그 간선은 선택하지 않는다는 의미를 함축함. 

 

2025.09.05 - [분류 전체보기] - [JAVA] 유니온 파인드 알고리즘

[JAVA] 유니온 파인드 알고리즘 <Disjoint Set>

 

기본적으로 정점과 간선에 대한 정보를 이용해서 간선에게 초점을 맞춰서 접근면 된다.

이 말이 지금은 별로 와닿지 않는데, Prim 알고리즘을 보고 나면 왜 하필 간선에 초점을 맞춰야 한다고 말했는지 느낄 수 있게 된다.

 

아무튼, 크루스칼 알고리즘은 가중치가 가장 작은 간선들만을 선택해나가면서 최소 신장 트리를 구현하는 것이다.

Kruskal 알고리즘 동작 원리

 

1. 간선 배열을 만들어서 입력 정보 전처리
2. 유니온 파인드 로직 - make()

3. 간선 배열을 가중치를 기준으로 오름차순 정렬
4. 유니온 파인드 로직 - find(), union()

 

코드 전문

SWEA 3124 - 최소 스패닝 트리

package src;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * @link: https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AZgruskKCQnHBIT9&contestProbId=AV_mSnmKUckDFAWb&probBoxId=AZjkGae6SiPHBIO0+&type=PROBLEM&problemBoxTitle=0826&problemBoxCnt=++3+
 * @performance: 2,184 ms, 115,960 kb
 * @note: Union-Find 복습 + Kruskal 복습
 * - Union-Find 로직에 Rank를 통한 최적화 및 경로 압축 최적화 적용
 * - 최대한 정석에 가깝게 구현했으니 해당 코드를 바탕으로 응용 연습해보면 될 듯.
 * - 물론 그냥 내 생각일 뿐
 * - 원래는 N개의 노드에 대해서 가장 저렴한 가중치를 가진 N - 1 개의 간선을 선택했을 때
 * - MST를 만족하지 못하는 경우가 있을거라는 이상한 착각에 빠졌었음 (혹시나 연결 안된 노드가 있다면? 노드에서 간선이 여러개 빠져 나가면 특정 노드는 연결 안되는 거 아님?)
 * @timecomplex: 아커만역함수 머시기 아무튼 빠름 근데 Arrays.sort() 써서 O(NlogN)일듯
 */
public class SWEA_3124 {
	// Union-Find
	public static int[] parents;
	
	public static void make() {
		for (int i = 0; i <= V; i++) {
			parents[i] = -1; // Union By Rank
		}
	}
	
	public static int find(int cur) {
		if (parents[cur] < 0) return cur; // 값이 -1이면 루트 노드를 의미, -2 이하이면 랭크가 증가한 부모 노드를 의미
		return parents[cur] = find(parents[cur]); // 경로 압축
	}
	
	public static boolean union(int a, int b) {
		int aP = find(a);
		int bP = find(b);
		
		// 이미 같은 집합
		if (aP == bP) return false;
		
		// 랭크가 서로 다를 때 (b가 더 큰 랭크) -> 왜 스왑? -> 자식으로 만드는 부분을 하나의 코드로 통일
		if (parents[aP] > parents[bP]) {
			// swap
			int temp = aP;
			aP = bP;
			bP = temp;
		}
		
		// 랭크가 서로 같을 때 -> a의 Rank를 증가 (-1, -2, -3 ... 작아질 수록 랭크가 큼)
		if (parents[aP] == parents[bP]) {
			parents[aP]--;
		}

		// 기본적으로는 b를 a의 자식으로 만듦.
		parents[bP] = aP;
		
		return true; // Union 연산 성공
	}
	
	// Kruskal -> 간선 배열 오름차순 정렬 + Union-Find로 간선 처리	
	public static class Edge implements Comparable<Edge> {
		int from;
		int to;
		int weight;
		
		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	public static Edge[] edges;
	
	// ---
	public static int V;
	public static int E;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			
			parents = new int[V + 1];
			edges = new Edge[E];
			
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int weight = Integer.parseInt(st.nextToken());
				edges[i] = new Edge(from, to, weight);
			}
			
			Arrays.sort(edges);
			make();
			
			int cnt = 0;
			long sum = 0;
			for (Edge e : edges) {
				int f = e.from;
				int t = e.to;
				int w = e.weight;
				
				if (!union(f, t)) continue; // union 결과가 !false = true -> 이미 트리 구조에 편입됨 또는 사이클?
				sum += w;
				if (++cnt == V - 1) break;
			}
			
			sb.append("#").append(test_case).append(" ").append(sum).append("\n");
		}
		System.out.print(sb);
	}

}

 

 

코드 해설

// Kruskal -> 간선 배열 오름차순 정렬 + Union-Find로 간선 처리	
public static class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;

    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.weight, o.weight);
    }
}

간선의 가중치로 정렬을 하기 위해서 Comparable 인터페이스를 구현해주면 된다.

 

for (Edge e : edges) {
    int f = e.from;
    int t = e.to;
    int w = e.weight;

    if (!union(f, t)) continue; // union 결과가 !false = true -> 이미 트리 구조에 편입됨 또는 사이클?
    sum += w;
    if (++cnt == V - 1) break;
}

정렬된 간선 배열에서 간선을 하나씩 꺼낸 뒤, 저장된 간선 정보(시작 정점 -> 도착 정점)를 이용해서 union() 연산을 수행함.

union() 연산의 결과가 false일 경우에는 이미 같은 트리(집합)임을 시사하는 것이기 때문에 해당 간선은 선택하지 않음. 

union() 연산이 성공하면 sum에 가중치를 더해주고 cnt가 V - 1개라면 종료해주면 된다. (간선의 개수는 정점 -1 개)