[Week10] MST 알고리즘(1) - Kruskal's Algorithm

MST (Minimum Spanning Tree)

그래프 이론에서 사용되며, 주어진 가중치 그래프에서 최소 비용으로 모든 정점을 연결하는 트리를 찾는 알고리즘

네트워크 설계, 전력 배선, 클러스터링 등 다양한 분야에서 활용된다. 

 

여러가지 MST 알고리즘이 있지만, 그 중에서도 가장 널리 사용되는 두 가지 알고리즘

1. Kruskal's Algorithm (크루스칼 알고리즘)

2. Prim's Algorithm (프림 알고리즘)

 

Kruskal's Algorithm (크루스칼 알고리즘)

기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 

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

 

크루스칼 알고리즘의 과정

1. 간선 가중치 기준 정렬

모든 간선을 가중치의 오름차순으로 정렬한다.

 

2. 최소 가중치 간선 선택

가장 작은 가중치를 가진 간선부터 시작하여 사이클을 형성하지 않으면 해당 간선을 선택한다.

 

3. 사이클 확인

선택한 간선이 사이클을 형성하는지 확인한다.

 

4. 선택된 간선 추가

사이클을 형성하지 않으면 해당 간선을 선택된 간선 집합에 추가한다.

 

5. 모든 정점을 포함할 때까지 반복

선택된 간선의 수가 𝑉−1이 될 때까지 위 과정을 반복한다. 여기서 𝑉는 정점의 수

 

예시

연결된 간선의 연결 비용이 낮은 순으로 위에서 부터 오름차순 정렬하고, 

다음 간선을 선택할때 사이클을 판단하기 위해 서로소 집합을 활용하기로 하였으므로, 

각 노드의 초기 집합은 아래와 같을 것이다.

 

비용이 적은 간선의 양 끝 노드를 선택하면서 

사이클이 존재하지 않는다면 Union 및 해당 간선 선택, 존재한다면 스킵하는 형태로 모

든 간선에 대하여 탐색이 끝날 때 까지 동작을 반복하면 된다. 

 

먼저, 첫 번째 간선을 선택한다. 두 노드 2, 3은 서로 독립된 집합이기 때문에 Union을 진행하고 간선도 선택한다.

 

마찬가지 방법으로 두 번째 간선을 선택한다. 두 노드 1, 6은 서로 독립된 집합이므로 Union 및 간선을 선택한다. 

 

5, 6번 노드를 간선에 대해서는 각 노드 5번의 최종 부모는 1, 6번의 최종 부모는 1로 두 집합이 이미 같은 집합에 속해있음을 알 수 있다.

그림에서 확인해보면 알겠지만, 두 노드를 연결하는 순간 사이클이 발생한다. 따라서, 이 경우는 그냥 스킵하면 된다.

 

나머지 노드에 대해서도 마찬가지로 진행해주면, 최종적으로 선택된 간선(빨간색)이 최소 신장트리(MST)가 됨을 확인할 수 있다.

 

구현 코드

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

/*
sample input(첫 줄의 첫 숫자는 정점의 개수, 두 번째 숫자는 간선의 개수).
6 9
1 6 5
2 4 6
1 2 7
3 5 15
5 6 9
3 4 10
1 3 11
2 3 3
4 5 7
 */

public class Kruskal {
	static int V, E;
	static int[][] graph;
	// 각 노드의 부모
	static int[] parent;
	// 최종적으로 연결된 최소 신장 트리 연결 비용.
	static int final_cost;

	public static void main(String[] args) {
		// 그래프의 연결상태(노드1, 노드2, 비용)를 초기화.
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		E = sc.nextInt();
		graph = new int[E][3];
		for (int i = 0; i < E; i++) {
			graph[i][0] = sc.nextInt();
			graph[i][1] = sc.nextInt();
			graph[i][2] = sc.nextInt();
		}
		parent = new int[V];
		final_cost = 0;

		// 간선 비용 순으로 오름차순 정렬
		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]);
	}
}

 

시간 복잡도

크루스칼 알고리즘은 O(ElogV)의 시간복잡도를 갖는다.

간단히 말하면 모든 가중치를 정렬하는데 걸리는 시간이 O(ElogE) 시간복잡도를 갖는데, 

크루스칼 알고리즘에서 이 연산보다 영향력이 있는 연산은 없기 때문에 최종적으로 O(ElogE)가 걸린다고 생각하는 것이다.

 

이때, 간선의 수는 최대 V^2개가 될 수 있으므로 O(logE) = O(logV^2) = O(2logV) = O(logV)로도 볼 수 있고,

최종적으로 O(ElogV)의 시간 복잡도를 갖는 것이다.

 

https://sskl660.tistory.com/72

[Java]크루스칼 알고리즘(Kruskal Algorithm)