Kruskal ( Union - Find ) :: 치매 방지 블로그

Kruskal ( Union - Find )

2021. 11. 12. 00:41

본 게시글은 권오흠 교수님의 영상을 공부하고 정리한 글 입니다.

[ Kruskal ]

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
- 가장 낮은 가중치를 먼저 선택한다.
- 사이클을 형성하는 간선을 제외한다. ( 사이클이 형성된다면 무시하고 다음 간선을 검색한다. ) ( Find ) 한다.
3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다. ( Union ) 한다.
4. 2~3 과정을 간선의 수가 n-1 개가 될 때까지 반복한다. ( 모든 정점의 개수는 n-1 개 )

그렇다면 우리가 알아야할 함수는

Q. ) 어떤 엣지가 추가될 때 사이클을 형성하는 간선인지 아닌지 어떻게 알 것인가? => Find

Q. ) 해당 간선을 어떻게 MST 집합에 추가 할 것인가? => Union

적은 숫자의 간선을 가지는 그래프라면 크루스칼 알고리즘으로 MST를 만드는게 적합하다.

크루스칼 알고리즘은 간선을 정렬하는 시간에 좌우되기 때문이다.

Union - Find는 거의 O(1) 에 가능하다.

어떠한 엣지가 사이클을 형성하는지 아닌지 알기 위해 우리는 각 정점을 서로소인 집합들로 표현해야한다.

- disjoint Set

엣지 ( h, g ) 를 선택하고자 할 때 집합 { h } 와 집합 { g } 는 서로 다른 집합에 속함으로 선택을 해도 사이클을 발생시키지 않는다.

엣지 ( h,g ) 를 선택하고 집합 { h } U { g } 를 합해준다. { h, g } .

...

가중치가 가장 작은 엣지들을 선택하다 보면

엣지 ( i ,g ) 를 선택하려고 할때 g 와 i 는 같은 집합에 속해 있으므로 선택하면 사이클을 형성하게 된다.

이 경우, 엣지 ( i, g ) 를 선택하지 않는다.

위와 같은 과정을 Union - Find 알고리즘이라고 한다.

물론 구현은 이처럼 간단하지 않다.

그렇다고 다르지도 않다.

[ Union- Find ]

그렇다면, 필요한것은 각각 노드(정점)가 서로소인 집합임을 표현하면서, Union 과 Find 이 두 가지 연산을 제공하는 자료구조 이다.

현재 까지 알려진 방법중에 가장 최선의 솔루션은 각 집합을 하나의 트리로 표현 하는 방법이다.

- 다만 , 우리가 아는 트리와는 다르게 트리의 각 노드는 자식노드가 아니라 부모 노드의 주소를 가진다. ( 상향식 트리 )

- 집합의 각 원소들이 트리의 노드가 되고, 누가 루트이고, 누가 누구의 부모인지는 중요하지 않다. 중요한것은 서로 연결되어 있다는것만 알면 된다.

이렇게 트리로 구현하는것이 뭔가 배보다 배꼽이 큰거 같아 거부감이 들 수 있으나,

사실 상향식 트리는 배열로 표현 가능하다.

배열로 표현 가능한 이유는 하향식 트리와 달리 각 노드는 부모의 노드 만 저장하기 때문이다.

이 때쯤 해서 한번 Kruskal 알고리즘 pseudo 코드로 정리해보자.

1 : A 를 공집합으로 시작해서

2 ~ 3 : 각각의 노드들을 서로소인 집합으로 만들어라( 배열로 표현 )

4 : 모든 엣지를 오름차순으로 정렬하고,

5 : for문의 반복 횟수가 모든 엣지라고 나와있지만 ( n-1 번이면 충분하다. MST에서 엣지의 개수는 n-1 )

6 : if 엣지 (u , v ) 에 대해서 u와 v 가 다른 집합에 있다면

7 ~ 8 : then 두 집합을 union 해줘라.

9 : 최종적으로 집합 A 를 return.

[ Find - Set ]

recursive 하게 구현할 수 있으며, 시간 복잡도는 O(h) 이고, 트리가 모두 일렬로 되어 있을땐 O(n)의 시간 복잡도를 가진다.

( Path Compression 을 통해서 트리의 높이를 낮게하는 알고리즘도 있어서 이를 통해 시간 복잡도를 거의 선형시간 O ( 1) 비슷하게 만들수 있다. )

여기서 parent[10] 배열은 각 노드의 집합을 트리로 구현한 배열.

int findSet(int (&parent)[10], int x) {
	if (parent[x] != x) {
		parent[x] = findSet(parent, parent[x]);
	}
	return parent[x];
}

[ Union ]

어떠한 두 트리를 합하는 가장 쉬운 방법은 한 트리의 루트를 다른 트리의 자식 노드로 만드는 것이다.

Union 알고리즘은 X, Y에다 Find-Set 을 해서 부모 위치만 바꿔주는거기 때문에

결국 Union의 시간 복잡도는 루트를 찾는 Find-set() 과 같다.

그렇다면 두 집합을 Union 할 때 집합의 높이 h를 작게 할 수 있다면, 시간 복잡도가 줄어들 수 있다. ( weighted Union )

- 노드 개수가 작은 트리의 루트를 노드 개수가 큰 트리의 자식으로 만들면 트리의 높이가 적어도 커지지는 않을 것이다.

( 물론 노드 개수가 많아도 높이가 작은 트리도 있지만, 너무 극단적인 예시이니 신경쓰지 않도록 한다. )

여기서 size 배열은 각 트리의 노드 개수를 위해 따로 카운트 하고 있는 배열.

void Union(int(&parent)[10], int a, int b) {
	a = findSet(parent, a);
	b = findSet(parent, b);
	if (::size[a] < ::size[b]) { 
		parent[a] = b; 
		::size[b] = ::size[a] + ::size[b];
	}
	else { 
		parent[b] = a;
		::size[a] = ::size[a] + ::size[b];
	}
}

[ 최종 구현 ]

ref :: http://https://m.blog.naver.com/ndb796/221230994142

동빈나 님의 블로그 글을 보고 참고한 Kruskal 알고리즘.

- 각 SET 별로 size 배열에 size를 저장하여 union 시 size가 큰 집합 밑으로 size가 작은 집합이 들어갈수 있도록 하였다.

[ 최종 구현 ] ▼

#include<iostream>
#include<vector>
#include<algorithm>

int parent[1001];
int p_size[1001];

class Edge {
public:
	int node[2];  // 엣지를 구성하고 있는 두 
	int distance;
	int p;

	Edge(int a, int b, int _distance): distance(_distance) {
		node[0] = a;
		node[1] = b;
	};
	bool operator <(Edge& edge) {
		return distance < edge.distance;
	}
};

int findSet(int* parent, int x) {
	if (parent[x] != x) {
		parent[x] = findSet(parent, parent[x]);
	}
	return parent[x];
}
void Union(int* parent, int a, int b) {
	a = findSet(parent, a);
	b = findSet(parent, b);
	if (p_size[a] > p_size[b]) {
		parent[b] = a;
		p_size[a] = p_size[a] +p_size[b];
	}
	else {
		parent[a] = b;
		p_size[b] = p_size[b] + p_size[b];
	}
}

int main() {
	int n = 7;
	int m = 11;

	std::vector<Edge> v;
	v.push_back(Edge(1, 7, 12));
	v.push_back(Edge(5, 7, 73));
	v.push_back(Edge(4, 7, 13));
	v.push_back(Edge(1, 4, 28));
	v.push_back(Edge(1, 2, 67));
	v.push_back(Edge(1, 5, 17));
	v.push_back(Edge(4, 2, 24));
	v.push_back(Edge(2, 5, 62));
	v.push_back(Edge(5, 6, 45));
	v.push_back(Edge(5, 3, 20));
	v.push_back(Edge(6, 3, 37));
	v.push_back(Edge(1, 7, 12));
	v.push_back(Edge(1, 7, 12));


	// 간선의 비용을 기준으로 오름차순 정렬
	std::sort(v.begin(), v.end());

	// 각 노드의 부모 노드를 배열로 나타냄.
	// 초기에는 자기 자신을 부모 노드로 설정.
	for (int i = 0; i < 7; i++) {
		parent[i] = i;
	}
	std::fill_n(p_size, 7, 1);

	int sum = 0; // 거리의 합.

	//모든 간선에 대하여 사이클이 발생하지 않는 경우 그래프를 합쳐준다.
	for (int i = 0; i < v.size(); i++) {
		
		int a = v[i].node[0];
		int b = v[i].node[1];

	// 간선의 끝점이 서로 다른 집합의 노드일때 두 노드의 집합 합쳐줌.
		if (findSet(parent, a) != findSet(parent, b) ){
			Union(parent,a,b);
			sum += v[i].distance;
		}
	}
	std::cout <<"최소 길이는 :: "<< sum;
	return 0;
}

'CS > Algorithm' 카테고리의 다른 글

최단 경로 ② ( Floyd - Warshall ) (0)	2021.11.17
최단 경로 & 그래프 문제 유형 (0)	2021.11.17
MST ( Minimum Spanning Tree ) - Kruskal , Prim (0)	2021.11.11
BFS ( Breadth First Search ) (0)	2021.11.10
DFS ( Depth First Search ) (0)	2021.11.10

치매 방지 블로그