최소 신장 트리 - 크루스칼

신장 트리?

스패닝 트리라고도 한다.

원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 뜻한다.

신장 트리의 조건

• 본래의 그래프의 모든 노드를 포함해야 함
• 모든 노드가 서로 연결
• 트리의 속성을 만족시킴(사이클이 존재하지 않음)

대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 존재한다.

크루스칼 알고리즘

그리디 알고리즘의 아이디어를 착안한 알고리즘

1. 각 정점간의 가중치를 List 혹은 배열로 만든다.
2. 모든 간선을 비용(가중치)을 오름차순으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. (그리디 알고리즘의 성질)
3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. ⇒ 사이클이 안 생기게 하려고

• 크루스칼 알고리즘은 간선의 개수가 E일 때 O(ElogE)로 동작한다.

🤔 사이클이 안 생기려면 어떻게 해야하지?

1. Union-Find 알고리즘을 사용하자.

Union-Find 알고리즘을 사용할 때 성능을 고려해야 한다.

최악의 경우 O(N)의 시간복잡도를 가질 수 있다.

🤔 성능 개선을 위한 어떤 방법이 있을까?

1. union-by-rank 기법

• 각 트리에 대해 높이(rank)를 기억해두고
• Union 시 두 트리의 높이가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙인다.
• 높이가 h - 1인 두 개의 트리를 합칠 때에는 한 쪽의 트리 높이를 1 증가시켜주고, 다른 쪽의 트리를 해당 트리에 붙여준다.

시간복잡도를 O(logN)으로 낮출 수 있다.

2. path compression

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
• Find를 실행한 노드는 이후부터는 루트 노드를 한 번에 알 수 있음

시간 복잡도는 O(M*LogN)이다.

크루스칼 알고리즘 구현

public class Kruskal {
	static int V, E; // 노드(V)와 간선(E)의 개수
	static int[][] graph;
	static int[] parent;

	public static void main(String[] args) {
		graph = new int[E][3];

		parent = new int[V];

		// [1]. 간선 비용 순으로 오름차순 정렬
		Arrays.sort(graph, (o1, o2) -> Integer.compare(o1[2], o2[2]));

		// makeSet
		for (int i = 0; i < V; i++) {
			parent[i] = i;
		}
		// 낮은 비용부터 크루스칼 알고리즘 진행
		for (int i = 0; i < E; i++) {
			// 사이클이 존재하지 않는 경우에만 간선을 선택한다(여기서는 최종 비용만 고려하도록 하겠다).
			if (find(graph[i][0] - 1) != find(graph[i][1] - 1)) {
				System.out.println("<선택된 간선>");
				System.out.println(Arrays.toString(graph[i]));
				union(graph[i][0] - 1, graph[i][1] - 1);
				final_cost += graph[i][2];
				System.out.println("<각 노드가 가리키고 있는 부모>");
				System.out.println(Arrays.toString(parent) + "\\n");
				continue;
			}
		}
		
		System.out.println("최종 비용 : " + final_cost);
		sc.close();
	}

	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a > b) {
			parent[a] = b;
		} else {
			parent[b] = a;
		}
	}

	private static int find(int x) {
		if (parent[x] == x)
			return x;
		else
			return find(parent[x]);
	}
}

예제 문제

• [ ] 최소 스패닝 트리
• [ ] 네트워크 연결
• [ ] 도시 분할 계획
• [ ] 행성 터널
• [ ] 별자리 만들기
• [ ] 다리 만들기 2
• [ ] 전력난
• [ ] 우주신과의 교감
• [ ] 나만 안되는 연애
• [ ] 행성 연결