Dasol Hong

I am a master’s student advised by Professor Hyun Myung at KAIST (Urban Robotics Lab).

[ALGO] Lect12. 서로소 집합 자료구조의 원리 및 크루스칼 알고리즘

3 minutes to read

강의 정보
강의명: [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고
교수: 성균관대학교 소프트웨어학과 허재필 교수님
사이트: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/course/



이번 시간에는 서로소 집합 자료구조의 원리에 대해 이해하고, 크루스칼 알고리즘을 적용해본다.


Disjoint Set, 서로소 집합

서로소 집합(Disjoint Set) 자료구조의 원리를 이해하고, 각 연산의 복잡도를 분석해본다.

개념

Disjoint Set이란 공통으로 중복되는 데이터가 없는 집합 $S_1, S_2, ... S_k$의 집합이다. 이때 각 집합 요소($S_k$)는 하나의 대표 값으로 표현될 수 있다.

\[C = \{S_1, S_2, ..., S_k\}\]


Operations

Disjoint Set에 대해 대표적으로 세 가지 Operations을 수행할 수 있다.

  • make-set(x): 멤버가 오직 x뿐인 새로운 집합을 생성한다. (∴ 대표값=x)
  • union-set(x,y): x, y로 대표되는 집합을 합집합한다.
  • find-set(x): x를 멤버로 갖는 집합의 대표값을 반환한다.


■ 응용

  • find-set(x)==find-set(y)인 경우, 두 멤버 x, y는 같은 집합에 포함되어 있다.>
  • connected components


Connected Components

image-20210912000406869

모든 edges에 대해 union-set 연산을 수행한 최종 결과로 connected components를 얻을 수 있다. ※ DFS에 비해 비효율적인 방법 ※


Implementation

■ Poor Implementation

Disjoint Set 자료구조를 구현하기위한 가장 단순한 방법으로 아래와 같이 2D array를 사용하는 방법을 생각해볼 수 있다.

image-20210912002226447

모든 vertex에 대한 대표자를 표시하여 구현할 수 있다.

  • 멤버 x의 집합을 알아내는 Finding 연산: $Θ(1)$>
  • union-set(x,y): $Θ(n)$ (∵ y가 속한 집합의 모든 멤버를 조사하여 x가 속한 집합의 대표자로 대표자값을 바꿔줘야 한다.)


■ Implementation

2D array를 사용하는 방식은 연산에 비용이 많이 소요되기 때문에 실제로는 아래와 같이 트리 구조로 Disjoint Set을 구현한다.

image-20210912002355644

대표자를 root값으로 두고, 멤버를 자식 nodes로 둔다.

  • union-set(x,y)을 수행하는 경우 단순히 root값을 자식 node로 추가해준다.

    image-20210912002500395

  • find-set(x): $O(h)$
  • union-set(x,y): $O(h)$

※ 일반적인 tree 자료구조는 부모가 자식 nodes를 point하지만, disjoint set을 구현하기 위한 tree 구조에서는 자식이 부모를 point하는 방향으로 구현된다. ※


● Generation of Disjoint Set

$n$개의 데이터에 대해 Disjoint Set를 구현하기 위해 길이가 $n$인 array를 생성한다.
※ 이때 parent의 초기값은 자기 자신이 된다. ※

parent = new int[n];
for(int i=0; i<n; i++)
    parent[i] = i;


● Find-set(x): x의 parent를 찾는 연산

parent값이 자기 자신이 될 때 까지 parent를 참조한다.

int Find_Set(int x)
{
    while(parent[x] != x)
        x = parent[x];
    return x;
}
\[\text{Complexity} : T_{\text{find}}(n) = O(h)\]


● Union-set(x,y): x와 y가 속한 집합의 합집합

x와 y의 root parent를 구한 뒤, y의 root parent의 parent값을 x의 root parent로 변경해준다.

void Union_Set(int x, int y)
{
    x = Find_Set(x);
    y = Find_Set(y);
    
    if(x!=y)
        parent[y] = x;
}
\[\text{Complexity} : T_{\text{union}}(n) = 2T_{\text{find}}(n)+Θ(1) = O(h)\]

※ 이때 height값이 큰 집합을 x로 사용하면 height값을 줄여 complexity를 작게 만들 수 있다. ※


Example

image-20210912002930085


■ union-set(1,3)

image-20210912003029896


■ find-set(1) and find-set(3)

image-20210912003123190


■ union-set(3,5)

image-20210912003216458


■ union-set(5,7)

image-20210912003302864


Worst-Case Scenario

같은 높이를 갖는 tree x, y를 union-set(x,y)하는 경우 tree x의 height가 커진다.

image-20210912004030362

이때 각 level에서 nodes의 개수를 세 보면 Pascal's triangle의 수와 같다는 걸 알 수 있다.


Pascal’s Triangle

\[\begin{pmatrix} n\\ m \end{pmatrix} = \begin{cases} 1 & \text{$m=0$ or $m=n$}\\ \begin{pmatrix} n-1\\ m \end{pmatrix} + \begin{pmatrix} n-1\\ m-1 \end{pmatrix} & \text{$0<m<n$} \end{cases}\\ =\frac{n!}{m!(n-m)!}\]

image-20210912004650630

이러한 Pascal’s Triangle을 알면 평균적으로 어느 정도 높이를 올라가야 root parent를 만날 수 있는지를 분석할 수 있다.

\[\sum_{k=0}^h{_nC_k} = \sum_{k=0}^h{\binom{h}{k}} = \sum_{k=0}^h{\frac{h!}{k!(h-k)!}} = 2^h = n\\ \sum_{k=0}^h{k\binom{h}{k}} = h2^{h-1}\\ ∴ \text{average depth} = \frac{h·2^{h-1}}{2^h}=\frac{h}{2}=\frac{\lg(n)}{2}\]

따라서 worst case일 때, height와 average depth의 complexity는 $O(\lg(n))$이다.
⇒ Disjoint Set이 효율적인 자료구조임을 확인할 수 있다.


서로소 집합과 크루스칼 알고리즘

크루스칼 알고리즘에서의 연결요소 관리를 서로소 집합으로 변경했을 때 복잡도를 개선할 수 있는 원리에 대해 이해하고 코딩으로 구현해본다.

Kruskal’s Algorithm using Disjoint Sets

Kruskal’s Algorithm은 minimum spanning tree 문제에서 사용할 수 있는 알고리즘 중 하나이다(이전 시간에 배웠다.). 이전에 배운 Kruskal’s Algorithm에서는 cycle을 체크하는 방식으로 DFS나 BFS와 같은 traversal algorithm을 사용했다. 이때 Disjoint Set의 자료구조를 Kruskal’s algorithm에 도입하면, algorithm의 complexity를 줄일 수 있다.

■ Example

image-20210912005007068


Analysis

■ Worst Case

아래 알고리즘에 대해 전체 edges 개수 $E$만큼 반복

  1. 두 vertex가 같은 집합에 포함되었는지를 확인 (find-set) : $O(\lg(V))$
  2. 서로 다른 집합에 속하는 경우
    1. 두 집합을 합집합화 (union-set): $O(\lg(V))$

따라서 Complexity는 다음과 같다.

\[E·(\lg(V) + \lg(V)) = 2E\lg(V)\\ \text{Complexity} = O(E\lg(V))\]

한편, Kruskal’s Algorithm을 적용하기에 앞서 모든 edges의 weights를 정렬하는 데에 필요한 비용은 $O(E\lg(E))=O(E\lg(V))$이다. (∵$E=V^2$)

따라서 최종 complexity는 다음과 같다.

\[\text{overall complexity} = O(E\lg(V) + E\lg(V)) = O(E\lg(V))\]

※ DFS(or BFS)를 이용한 Kruskal’s algorithm의 complexity $O(EV)$에 비해 효율적임을 알 수 있다. ※



References

  1. [집콕]인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고-비선형 자료구조, K-MOOC: http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/courseware/1158909c057347478d7386a2b7e97214/e9d736660cad4f76bcb9a05974fe0bf2/1?activate_block_id=block-v1%3ASKKUk%2BSKKU_46%2B2021_T1%2Btype%40vertical%2Bblock%4052b62ff6da2147c9a8a65a6056681d91



참고