그래프 노드간 연결 파악을 위한 Dynamic Connectivity 알고리즘

동적 연결 알고리즘 (Dynamic Connectivity)

조대협 (http://bcho.tistory.com)

요즘 알고리즘이 대세라 기초를 다지는 차원에서 다시 알고리즘을 보고 있는데, 오늘은 동적 연결 알고리즘에 대해서 공부한 내용을 간략하게 정리해본다.

동적 연결 알고리즘은 노드끼리 연결이 되어 있는지를 찾는 알고리즘이다.

각 도시간에 연결이 되어 있는지, SNS에서 친구끼리 서로 연결이 되어 있는지와 같은 연결성만을 판단한다.

예전에 이러한 문제를 그래프 형태의 자료구조를 이용해서 풀려고 했는데, 여기서 문제의 핵심은 노드 A와 B가 연결되었는지만 판단하면 된다. 즉 자료 구조상에서, 어떤 노드가 어떤 노드와 인접해 있는지등은 표시할 필요가 없다. 아래 그림을 보자, 아래 그림에서 1과 5는 연결이 되어 있다. (1->2->5 경로) 4,2는 연결되어 있지 않다.

이 처럼 노드간의 연결 여부만 판단 하는 것이 동적 연결 알고리즘 (Dynamic Connectivity)문제이다.

 

QuickUnionFind

이를 구현하는데 몇가지 알고리즘이 있는데, 가장 간단한 알고리즘으로는 QucikUnionFind라는 알고리즘이다.

QuickUionFind 알고리즘은 아래와 같이 일차원 배열을 이용해서 구현하는데, 배열의 Index가 노드명, 그 값이 ID이다. ID가 같은 노드들은 서로 연결되어 있는 것으로 취급 한다.

이런식으로 된다. 값이 9,8,7 3의 컴포넌트로 나뉘어 짐을 알 수 있다.

이 알고리즘의 경우 구현은 쉽지만, 매번 연결을 추가할때 마다 ID값을 스캔해서, 같은 컴포넌트에 있는 노드의 ID값을 매번 변경해야 하기 때문에 성능이 매우 낮다. O(N^2)의 복잡도를 갔는다.

Tree (QuickFindUF)

그래서 이를 보완하는 알고리즘으로는 Tree를 사용하는 방법이 있는데, Tree의 값에는 이 노드와 연결된 상위 노드의 인덱스 값을 가지게 한다.

이때 주의해야 하는 것이, Tree에서 표현되는 상하위 노드의 연결 내용은 중요하지 않다. 실제로 그림에서 1,3 노드간에는 연결은 없지만, 필요하다면 Tree에서는 1,3 노드를 연결해서 표현하되, 1,3이 하나의 트리에만 있으면 된다.

헷갈릴 수 있는 부분이, 각 노드간의 연결을 온전히 저장하는 것이 아니라, 컴포넌트에 어떤 노드가 있는지를 저장하는 것이기 때문에, 각 노드 간의 연결성에 초점을 맞출 필요가 없다. 

위의 그래프 저장 결과는 배열에서 다음과 같다.

 

여기서 노드가 연결되어 있는지를 찾으려면, root 노드가 같은지를 비교하면 된다.

즉, 노드 9,5가 연결되어 있는지 찾으려면 9 --> 5 까지의 경로를 트래버스 하는 것이 아니라, 9와 5의 root 노드(1)을 찾아서 동일한지를 비교하면 된다.

WeightTree

위의 트리 기반의 알고리즘의 경우, Depth가 비약적으로 길어질 수 있는 문제가 있는데, 이를 해결하기 위해서는 WeightTree라는 알고리즘을 사용할 수 있다. 이 알고리즘은 두개의 트리를 병합할때, 항상 작은 트리를 큰 트리의 루트에 붙이게 함으로써 전체 트리의 Depth를 줄이는 방법이다.

아마 이 알고리즘을 보지 않았더라면, Dynamic Connectivity 문제도 Node *  기반의 자료 구조를 만들어서 DFS(깊이 우선 검색)으로 해결하려고 하지 않았을까? (성능은 무지 안나오겠지)

참고자료 및 소스

http://algs4.cs.princeton.edu/15uf/