Kruskal(크루스칼) 알고리즘

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

Kruskal(크루스칼) 알고리즘

크루스칼 알고리즘은 아래의 순서대로 작동한다.

1. 그래프의 각 꼭지점이 각각 하나의 나무(자료구조의 tree)가 되도록 하는 숲 F을 만든다.

2. 모든 변을 원소로 갖는 집합 S를 만든다.

3. S가 비어있지 않는 동안

1) 가장 작은 가중치의 변을 S에서 하나 빼낸다.

2) 그 변이 어떤 두개의 나무를 연결한다면 두 나무를 연결하여 나무로 만든다.

3) 그렇지 않다면 그 변은 버린다.

알고리즘이 종료됐을 때, 숲 F는 하나의 최소비용 생성나무만을 가지게 된다.

크루스칼 알고리즘의 다른 형태가 있다. 그래프에서 변을 제거하는 방식이다.

1) 그래프에서 꼭지점 또는 나무를 분리해 내지 않는 최대 가중치의 변을 제거한다.

2) 그래프에 n-1개의 변만 남을 때까지 1을 반복한다.

3) 그래프에 n-1개의 변이 남으면 최소 비용 생성 나무이다.

출처 : 위키백과

- 에지들을 가중치의 오름차순으로 정렬한다.

- 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 Cycle(사이클)을 형성하면 선택하지 않는다.

- n-1개의 에지가 선택되면 종료한다.

왜 MST가 찾아지는가?

- Kruskal의 알고리즘의 임의의 한 단계를 생각해보자.

- A를 현재까지 알고리즘이 선택한 에지의 집합이라고 하고, A를 포함하는 MST가 존재한다고 가정하자.

사이클 검사

예 : 

초기상태 : 선택된 에지 없음

각각의 연결 요소를 서로 연결된 하나의 집합으로 표현

1) 가중치가 최소인 에지(c, f)를 고려한다.

2) c, f가 서로 다른 집합에 속하면

3) 에지(c, f)를 선택하고 c, f가 속한 집합을 합집합하여 하나의 집합으로 만듬 -> {c, f}

-> 그 다음

1) 가중치가 최소인 에지(g, i)를 고려한다.

2) g와 i가 서로 다른 집합에 속하면

3) 에지(g, i)를 선택하고 g와 i가 속한 집합을 합집합하여 하나의 집합으로 만듬 -> {g, i}

-> 그 다음

1) 가중치가 최소인 에지(e, f)를 고려한다.

2) e와 f가 서로 다른 집합에 속하면

3) 에지(e, f)를 선택하고 e와 f가 속한 집합을 합집합하여 하나의 집합으로 만듬 -> {e, f}

-> 그 다음

1) 가중치가 최소인 에지(d, h)를 고려한다.

2) d와 h가 서로 다른 집합에 속하면

3) 에지(d, h)를 선택하고, d와 h가 속한 집합을 합집합하여 하나의 집합으로 만듬 -> {d, h}

... 반복

최종 집합은 {a, b, c, f, e, d, g, h, i} -> 싸이클을 이루지 않는 집합이 완성됨

의사코드

MST-KRUSKAL(G, w){
	A <- 0
	for each vertex v∈V[G]	// 각각의 노드들을 유일한 원소로 가지는 집합을 만들어라.
		do MAKE-SET(v)
	sort the edges of E into nondecreasing order by weight w
	for each edge(u, v)∈E, taken in nondevreasing order by weight
		do if FIND-SET(u) != FIND-SET(v)  // FIND-SET(v) : 노드 v가 속한 집합을 찾아라
			then A <- A∪{(u, v)}
				UNION(u, v)	// u와 v가 속한 두 집합을 하나로 합친다.
	return A
}

FIND-SET(v)

- 자신이 속한 트리의 루트를 찾음

FIND-SET(v){
	if x != p[x]
		then p[x] <- FIND-SET(p[x])
	return p[x]
}

FIND-SET-PC(x) {
	while x != p[x] do
		p[x] <- p[p[x]];
		x <- p[x];
	end.
	return p[x];
}

UNION(u, v)

- 한 트리의 루트를 다른 트리의 루트의 자식노드로 만듬

UNION(u, v){
	x <- FIND-SET(u);
	y <- FIND-SET(v);
	p[x] <- y;
}

Weighted Union

- 두 집합을 union 할때 작은 트리의 루트를 큰 트리의 루트의 자식으로 만듬(여기서 크기란 노드의 개수)

- 각 트리의 크기(노드의 개수)를 카운트하고 있어야 한다.

WEIGHTED-UNION(u, v){
	x <- FIND-SET(u);
	y <- FIND-SET(v);
	if size[x] > size[y] then
		p[y] = x;
		size[x] <- size[x] + size[y];
	else
		p[x] = y;
		size[y] <- size[y] + size[x];
}

Weighted Union with Path Compression(WUPC)

- M번의 union-find 연산의 총 시간 복잡도는 O(N+M log*N)

- 여기서 N은 원소의 개수

- 거의 선형시간 알고리즘. 즉, 한번의 Find 혹은 Union이 거의 O(1) 시간

- log*N = (log log log ... logN) = 1이 될때까지 몇번해야한는가 횟수

Kruskal의 알고리즘 시간복잡도

Initialize A : O(1)

First for loop : |V| MAKE-SETs -> O(n)

Sort E : O(|E| log2|E|) -> mlogm

Second for loop : O(|E| FIND-SETs and UNIONs? -> O(1)

따라서 O(|E| log2|E|)

소스 코드(Java)