[알고리즘] MST - Kruscal 알고리즘

 

 

 Kruscal 

Minimum Spanning Tree (최소 신장 트리)

최소 신장 트리를 알기 전에 신장 트리 개념에 대해서 알 필요가 있습니다.

신장 트리 (Spanning Tree)
: 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

여기서 사이클이 존재하지 않는 다는 것은 바퀴를 돌아 제자리로 올 수 있다는 것입니다.

신장 트리에는 사이클이 없어야 합니다.

 

최소 신장 트리는 이러한 신장 트리들 중에서 가중치의 합이 가장 작은 신장 트리를 이릅니다.

MST 라고 하며 이러한 MST 를 구성할 수 있는 알고리즘은 2가지가 있습니다.

바로 이번 포스팅에서 소개할 Kruskal 알고리즘과 다음 포스팅에서 소개할 Prim 알고리즘 입니다.

 

 

Kruskal 특징

그리디 알고리즘을 이용하여 MST 를 구합니다.

1. 가중치를 기준으로 간선들을 오름차순으로 정렬한다.
2. 정렬된 간선들 중에서 사이클이 생기지 않는 간선을 선택한다. 

Kruskal 알고리즘은 간선의 개수가 E 개 일때, O(ElogE) 의 시간복잡도를 가집니다.

왜냐하면 간선을 정렬하는 데 걸리는 시간복잡도가 O(ElogE) 이기 때문입니다.

 

 

makeSet()

private static void makeSet() {
    for (int i = 1; i <= V; i++) parents[i] = i;
} // end makeSet

부모 노드를 표시하는 parents 배열을 초기에 세팅하는 것입니다.

이는 각 노드를 서로소 집합으로 구성하는 것과 같습니다. 따라서 이 상태에서는 자신의 부모 노드는 자신이 됩니다.

 

 

findSet()

private static int findSet(int x) {
    if (x == parents[x]) return x;
    return parents[x] = findSet(parents[x]);
} // end findSet

자신의 부모 노드를 찾는 함수입니다.

 

 

union()

private static boolean union(int x, int y) {
    int px = findSet(x);
    int py = findSet(y);

    if (px == py) return false;

    if (px < py) parents[py] = px;
    else parents[px] = py;

    return true;
} // end union

서로소 집합 2개를 합집합으로 만드는 함수 입니다.

만약 부모 노드가 같다면 이는 같은 집합에 속하는 것이므로 return false 하고

그렇지 않은 경우에는 인덱스가 큰 것의 부모를 작은 것으로 설정합니다.

 

 

Kruskal 알고리즘 input.txt

2
5 10
0 1 5
0 2 10
0 3 8
0 4 7
1 2 5
1 3 3
1 4 6
2 3 1
2 4 3
3 4 1
7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51

 

 

Kruskal 알고리즘 코드

package first.p05;


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


public class KruskalTest {
	static int ans, T, V, E;
	static Edge[] edges;
	static int[] parents;


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/first/p05/input/kruskal.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken()); // 노드의 수
			E = Integer.parseInt(st.nextToken()); // 간선의 수

			// 초기화
			ans = 0;
			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);
			}

			parents = new int[V + 1]; // 0 dummy

			// 1. 서로소 집합 만들기
			makeSet();

			// 2. 정렬
			Arrays.sort(edges, (e1, e2) -> e1.weight - e2.weight);

			// 3. MST 찾기
			for (Edge edge : edges) {
				if (union(edge.from, edge.to)) ans += edge.weight;
			}

			// MST 값 출력
			System.out.println("#" + t + " " + ans);

		}

	} // end main


	private static void makeSet() {
		for (int i = 1; i <= V; i++) parents[i] = i;
	} // end makeSet


	private static int findSet(int x) {
		if (x == parents[x]) return x;
		return parents[x] = findSet(parents[x]);
	} // end findSet


	private static boolean union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);

		if (px == py) return false;

		if (px < py) parents[py] = px;
		else parents[px] = py;

		return true;
	} // end union


	static class 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 String toString() {
			return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
		}

	} // end Edge
}

출력

우선 Edge[] 로 edges 간선 배열을 만듭니다. 해당 간선 배열에는 그래프의 방향과 가중치가 들어있습니다.

각각의 노드들을 서로소 집합으로 만들고, 가중치를 기준으로 간선 배열을 정렬합니다.

간선 배열만큼 반복문을 돌며 해당 간선에 있는 노드 두 개가 아직 합집합이 아니라면 가중치를 합에 더합니다.

 

 

 

 

 

# 그래프 이론 # kruskal # Kruskal 알고리즘 # kruskal 시간복잡도

---