[알고리즘] 16. LCA, Boruvka's Randomized MST Algorithm

[알고리즘] 16. LCA, Boruvka's Randomized MST Algorithm

1. LCA (Lowest Common Ancestor)

Preprocessing

모든 노드에 레벨 정보가 기록된 트리에서 두 노드 a, b의 최소 공통 조상 x를 찾아보자. 먼저 각 노드들이 1, 2, 4, 8, 16, ..., $2^j$ 칸 위의 조상의 번호를 저장하는 과정이 필요하다. \texttt{A[i][j]} 는 $i$번 노드의 $2^j$ 칸 위의 조상의 번호를 저장한다. 이때 $j$의 값은 0부터 $log n$까지이다.

Base: $\texttt{A[i][0]}$: 나의 부모의 ID 값

Step: $\texttt{A[i][j+1] = A[A[i][j]][j]}$: 모든 노드가 $2^j$ 칸 위의 ID를 안다고 가정하면 $2^{j+1}$칸 위의 ID는 $2^j$칸 위로 올라간 뒤 ($\texttt{A[i][j]}$로 온 뒤) 이 노드에서 한번 더 $2^j$칸을 올라가면 된다.

Findnig LCA

이제, 위에서 생성한 배열 A를 이용하여 노드 a와 b의 LCA를 찾아보자.

먼저 a를 b와 같은 레벨로 맞춘다. 이때 레벨의 이동은 2의 거듭제곱꼴로 이루어진다. 예를 들어 a가 b보다 11칸 아래에 있으면, $11=1011_{(2)}$ 이므로 8칸, 2칸, 1칸 위로 올라가야 된다.

a $\rightarrow a_1$ = $\texttt{A[a][3]}$

$a_1\rightarrow a_2$ = $\texttt{A[$a_1$][1]}$

$a_2\rightarrow a'$ = $\texttt{A[$a_2$][0]}$

이렇게 a를 올려서 b와 같은 높이에 오는 노드를 $a'$이라 하자. 이제 $a'$, b 모두 같은 레벨에서 위로 점프를 하면서 공통 조상 여부를 판단하자. $\texttt{A[a'][j], A[b][j]}$의 값이 같은지 다른지 판단한다. 만약 같으면 j를 하나 감소시키고, 다르면 그 노드에서 정지한다. 정지한 노드가 j = t일때라고 가정하면 노드 t에서부터 다시 위의 과정을 반복해서 $\texttt{A[A[a'][t]][j], A[A[b][t]][j]}$ 의 값이 같은지 다른지를 판단하면 된다. 이때 j의 초기값은 $log n$이고 j가 0이 되면 알고리즘을 종료한다.

Preprocessing 단계는 $O(nlogn)$이 소요되고, 그걸로 LCA를 찾는 과정은 $O(n)$이 소요된다.

2. Boruvka's MST Algorithm: Randomized MST

Boruvka의 알고리즘은 각 노드마다 weight가 가장 작은 엣지를 선택하고, Connected Component를 하나의 노드로 합치는 과정을 전체에서 하나의 노드만 남을때까지 반복하는 것이다. 이때 각 노드마다 선택한 엣지는 MST에 들어가게 되고, 각 라운드마다 노드의 개수가 1/2이 된다.

이제 Randomized MST를 찾아보자. 그래프 G에서 Boruvka 알고리즘을 3번 돌려서 노드의 개수를 1/8로 만든 그래프를 $G_1$이라 하자. $G_1$에서 엣지를 50\% 확률로 선택해서 엣지의 개수를 1/2로 줄인다. 전체 알고리즘을 재귀로 돌린 결과를 F라 하자. (MSF) F에서 Heavy Edge들을 제거하고, 다시 전체 알고리즘을 재귀로 돌린 뒤 그 결과를 $G_2$이라 하자. 그럼 최종 정답은 $G_1 \cup G_2$ 이다. (Heavy Edge란 그 엣지를 포함한 사이클 내에서 그 엣지를 제외한 나머지 엣지들의 weight들 보다 큰 엣지를 의미한다. Heavy Edge를 찾기 위해서 edge weight에 minimum 값들을 넣으면서 LCA를 하면 제일 작은 edge weight를 알 수 있다.)

from http://pongkijoa.tistory.com/26 by ccl(A) rewrite - 2021-12-28 20:27:07