개요
- Union-Find 알고리즘은 아래의 두 가지 메소드를 제공한다.
- Find – 특정 원소가 어떤 subset에 있는지 판단한다. 이것은 두 원소가 같은 subset에 속해 있는지 판단하는데 사용되기도 한다. 보통 subset의 대표 vertex index를 반환하게 구현한다.
- Union – 두 개의 subset을 하나의 subset으로 통합한다. 두 subset이 같은 대표 vertex index를 갖도록 구현한다.
- Disjoint Set Data Structure는 주어진 set을 몇 개의 disjoint subset으로 나누는 것인데 대표적으로 위의 두 메소드를 사용한다. 그리고 Disjoint Set Data Structure를 이용하면 어떤 graph에서 cycle이 존재하는지 판단할 수 있다. (단, 적어도 vertex의 self loop는 없어야 한다)
방법
- Cycle이 포함되어 있는지 여부는 아래와 같이 Find 메소드와 Union 메소드를 이용하면 알 수 있다.
|
모든 edge에 대해 Find 메소드를 적용해 edge의 양쪽 vertex가 같은 subset에 속하는지 체크한다. 1) 같은 subset에 속한다면 이미 다른 경로를 통해 연결된 지점이므로 이번 edge를 통해 cycle이 된다. 2) 같은 subset에 속하지 않았다면 이번 edge를 통해 연결되므로 Union 메소드를 통해 같은 subset으로 만들어준다. |
- 이를 위해 각 vertex의 부모를 저장하는 배열을 만든다.
- Find 메소드는 어떤 원소의 부모의 부모를 따라 최종 root를 반환한다. Root가 같다면 결국 같은 subset으로 판단한다.
- Union 메소드는 한쪽 root의 부모를 다른 쪽 root로 지정해주면 된다.
예제
- 예를 들어 아래와 같은 그래프가 있다고 하자. Vertex 0, 1, 2의 parent는 모두 -1로 초기화한다. 이는 각각의 부모는 없는 상태이고 자기 자신이 disjoint subset이라는 뜻이다.
- 첫 번째, edge 0-1을 선택하자. 둘 다 서로 다른 subset이므로 union을 한다. Union을 한 뒤에는 0의 부모가 1이 된다. (그 반대라도 상관없다) 이제 subset {0, 1}의 대표가 1이 된 것이다.
- 두 번째, edge 1-2를 선택하자. 둘 다 서로 다른 subset이므로 union을 한다. Union을 한 뒤에는 1의 부모가 2가 된다. 이제 subset {0, 1, 2}의 대표로 2가 되었다.
- 세 번째, edge 0-2를 선택하자. 0의 부모는 1이고 1의 부모는 2이므로 결국 0과 2는 같은 subset이다. 이로써 cycle이 존재한다는 것을 알게 되었다.
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <stdio.h> #include <stdlib.h> typedef struct { int src; int dst; } Edge; typedef struct { int V; // Number of vertices int E; // Number of edges Edge* edge; // graph is represented as an array of edges } Graph; // find the root of the specified element's subset int findRoot(int parent[], int i) { if (parent[i] == -1) return i; return findRoot(parent, parent[i]); } // do union of two subsets void doUnion(int parent[], int x, int y) { int xRoot = findRoot(parent, x); int yRoot = findRoot(parent, y); parent[xRoot] = yRoot; } // check whether a given graph contains cycle or not int containsCycle(Graph* graph) { int* parent = (int*)malloc(graph->V * sizeof(int)); // initialize all subsets as single element sets for (int i = 0; i < graph->V; ++i) parent[i] = -1; // find subset of both vertices of every edge, // if both subsets are same, then there is cycle in graph. for (int i = 0; i < graph->E; ++i) { int x = findRoot(parent, graph->edge[i].src); int y = findRoot(parent, graph->edge[i].dst); if (x == y) return 1; doUnion(parent, x, y); } return 0; } int main() { /* Let us create following graph 0 | \ | \ 1---2 */ Graph* graph = (Graph*)malloc(sizeof(Graph)); graph->V = 3; graph->E = 3; graph->edge = (Edge*)malloc(sizeof(Edge) * graph->E); // add edge 0-1 graph->edge[0].src = 0; graph->edge[0].dst = 1; // add edge 1-2 graph->edge[1].src = 1; graph->edge[1].dst = 2; // add edge 0-2 graph->edge[2].src = 0; graph->edge[2].dst = 2; if (containsCycle(graph)) printf("graph contains cycle\n"); else printf("graph doesn't contain cycle\n"); return 0; } |
Union-Find의 개선
- 앞선 방법에서 Find와 Union 메소드는 worst case에서 O(n) 또는 O(V)이 된다. (물론 cycle detection 메소드는 거기에 또 E 만큼 곱해야 한다)
- Worst case란 parent tree가 skew되어 있을 경우인데 이때는 root를 찾는 과정이 모든 노드를 탐색하는 것과 동일하기 때문이다. 예를 들면 {0, 1, 2, 3}에 대해서 아래와 같은 경우이다.
- 이를 개선하기 위해서는 tree를 balanced하게 구성하는 것이 중요하다. 그러면 worst case에서도 O(log n)이 될 수 있다.
Union by Rank
- 첫 번째 개선 방법으로 "Union by Rank" 방법이 있다. 이 방법은 두 subset (tree)를 union할 때 depth가 낮은 쪽은 높은 쪽의 root 바로 밑에 넣는 방법이다. 그러면 전체 depth는 높은 쪽의 depth가 된다. 다만 양측의 depth가 같을 경우에는 어쩔 수 없이 depth가 하나 증가한다.
- 그런데 왜 depth나 height라는 용어 대신 rank라는 용어를 사용하냐 하면, 뒤에 언급할 Path Compression 방법과 같이 사용할 때는 rank가 꼭 height/depth와 일치하지는 않기 때문이다. (Path Compression에서 tree를 flatten한 뒤에 rank 조절을 안한다)
- 예를 들어 위에서 skewed되었던 {0, 1, 2, 3}에 대해 Union by Rank 기법을 적용하면 아래와 같이 된다.
- 큰 차이는 아니지만 코드의 편의상 parent[] 초기값을 -1이 아닌 자기 자신 값으로 한 점도 유의하자.
Path Compression
- 다음으로 "Path Compression" 방법이 있다. 이 방법은 Find 메소드가 호출될 때 tree를 flatten하게 만드는 방법이다.
- 임의의 원소 x에 대한 Find 메소드가 호출되면 root를 구한 뒤 x의 parent를 root로 바꾼다.
- 그러면 원소 x가 곧바로 root의 자식이 되어서 x와 그의 자손들의 이후 Find 메소드가 간단해진다.
- 예를 들어 {0, 1, 2, …, 9}가 아래 왼쪽과 같이 tree를 형성하고 있다면 Find 메소드 호출 후 오른쪽 그림처럼 된다.
Code (Union by Rank and Path Compression)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <stdio.h> #include <stdlib.h> typedef struct { int src; int dst; } Edge; typedef struct { int V; // Number of vertices int E; // Number of edges Edge* edge; // graph is represented as an array of edges } Graph; // find the root of the specified element's subset // (uses Path Compression) int findRoot(int parent[], int i) { // find root and make root as parent of i if (parent[i] != i) parent[i] = findRoot(parent, parent[i]); return parent[i]; } // do union of two subsets (uses Union by Rank) void doUnion(int parent[], int rank[], int x, int y) { int xRoot = findRoot(parent, x); int yRoot = findRoot(parent, y); // attach smaller rank tree under root of high rank tree if (rank[xRoot] < rank[yRoot]) parent[xRoot] = yRoot; else if (rank[xRoot] > rank[yRoot]) parent[yRoot] = xRoot; // if ranks are same, then make one as root and increment // its rank by one else { parent[yRoot] = xRoot; rank[xRoot]++; } } // check whether a given graph contains cycle or not int containsCycle(Graph* graph) { int* parent = (int*)malloc(graph->V * sizeof(int)); int* rank = (int*)malloc(graph->V * sizeof(int)); // initialize all subsets as single element sets for (int i = 0; i < graph->V; ++i) { parent[i] = i; rank[i] = 0; } // find subset of both vertices of every edge, // if both subsets are same, then there is cycle in graph. for (int i = 0; i < graph->E; ++i) { int x = findRoot(parent, graph->edge[i].src); int y = findRoot(parent, graph->edge[i].dst); if (x == y) return 1; doUnion(parent, rank, x, y); } return 0; } int main() { /* Let us create following graph 0 | \ | \ 1---2 */ Graph* graph = (Graph*)malloc(sizeof(Graph)); graph->V = 3; graph->E = 3; graph->edge = (Edge*)malloc(sizeof(Edge) * graph->E); // add edge 0-1 graph->edge[0].src = 0; graph->edge[0].dst = 1; // add edge 1-2 graph->edge[1].src = 1; graph->edge[1].dst = 2; // add edge 0-2 graph->edge[2].src = 0; graph->edge[2].dst = 2; if (containsCycle(graph)) printf("graph contains cycle\n"); else printf("graph doesn't contain cycle\n"); return 0; } |
- findRoot() 메소드에서는 재귀적인 성격 때문에 최초의 find element 뿐만 아니라 그 부모, 조상까지 모두 root 밑에 바로 붙는 flatten이 이루어진다. (라인 21)
- 이렇게 Union by Rank와 Path Comression 방법을 동시에 사용하면 worst case에서도 O(log n)이 된다. 사실 이보다도 적다. Amortized한 time complexity는 거의 상수 시간이다.
