Union-Find(1) : Dynamic Connectivity

Dynamic Connectivity

• Union Find 알고리즘을 이해하기 위해서는 Dynamic Connectivity에 대한 기본 개념이 필요합니다.
  • union : 두 object를 연결합니다.
  • connected : 두 object가 연결되어 있는지에 대해 응답합니다.
• 초기 세팅에 의하면 0과 7은 연결되어 있지 않습니다.
  하지만 다른 object들이 연결됨에 따라 두 object 또한 간접적으로 연결되게 되었습니다.

 

Modeling the connections

• is connected to, 즉 연결되었다는 표현은 크게 세 가지를 포함할 수 있습니다.
  • 1) Reflexive : 자기 자신에게는 항상 연결되어 있는 셈이죠.
  • 2) Symmetric(대칭적) : p가 q에 연결되어 있다면, q도 p에 연결되어 있습니다.
  • 3) Transitive(전달적?) : p가 q에 연결되어 있고, q가 r에 연결되어 있다면, p는 r에 연결되어 있습니다.
• Connected components : 상호 연결된 최대한의 세트!
  • 즉 연결 되어있는 모든 노드(object)를 묶어놓은 집합을 뜻합니다.

 

Implementing the operations

• 만약 두 개의 object가 한 개의 connected component에 속하지 않는 경우, 둘을 union하면 어떻게 될까요?
  • 두 개의 connected components 전체가 연결됩니다.
  • 그림에서 볼 수 있는 것처럼 한 개의 연결고리만 생기더라도 관련된 object들이 모두 간접적으로 연결되기 때문이죠.
  • 결과적으로 이런 union이 실행될 때마다 connected components의 개수는 줄어들겠네요.

 

출처: Coursera, Algorithms, Part 1, Princeton University