본 게시글은 권오흠 교수님의 영상을 공부하고 정리한 글 입니다.
[ 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; }
관련 알고리즘 문제 .
< Kruskal 문제 >
프로그래머스 섬 연결하기 문제. https://blog.naver.com/wldlf94/222526662101
백준 최소 스패닝 트리 - 1197번 https://www.acmicpc.net/problem/1197
백준 네트워크 연결 - 1922번 https://www.acmicpc.net/problem/1922
'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 |