이번 글에서는 그래프(Graph)의 연결요소(Connected Components)를 찾아내는 기법을 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

연결요소란 원그래프 $G$ 가운데 노드와 엣지가 서로 겹치지 않는 부그래프이되, 부그래프 내 모든 노드쌍에 대해 경로가 존재하는 걸 가리킵니다. 연결요소를 구축하는 기법은 디스조인트 셋(Disjoint Set)으로 구현하게 됩니다. 예컨대 원그래프 $G$에 아래와 같은 연결요소들 4개가 있다고 칩시다.

연결요소를 구축하는 알고리즘은 엣지를 중심으로 수행합니다. 위 그래프의 엣지 리스트는 다음과 같습니다.

• ($b, d$)
• ($e, g$)
• ($a,c$)
• ($h,i$)
• ($a,b$)
• ($e,f$)
• ($b,c$)

우선 모든 노드에 대해 make-set 연산을 수행합니다. 각 노드를 유일한 원소로 하는 새로운 셋을 만든다는 뜻입니다.

• {$a$}, {$b$}, {$c$}, {$d$}, {$e$}, {$f$}, {$g$}, {$h$}, {$i$}, {$j$}

이제 그래프 내 모든 엣지를 하나씩 검토합니다. 우선 첫번째 엣지인 ($b,d$)를 보겠습니다. 노드 $b$가 속한 셋의 대표값(루트노드)을 찾습니다(find 연산). 그리고 $c$의 대표값을 찾습니다. 둘을 비교하니 서로 다르므로($b≠c$) 두 셋을 합칩니다(union 연산). 결과는 다음과 같습니다.

• {$a$}, {$b,d$}, {$c$}, {$e$}, {$f$}, {$g$}, {$h$}, {$i$}, {$j$}

다음 ($e,g$)를 보겠습니다. $e$가 포함된 셋과 $g$의 셋이 서로 다르므로 두 셋을 합칩니다. ($a,c$), ($h,i$), ($a,b$), ($e,f$)도 마찬가지입니다. 다음과 같습니다.

• {$a,b,c,d$}, {$e,f,g$}, {$h,i$}, {$j$}

마지막으로 ($b,c$)를 보겠습니다. $b$가 포함된 셋의 루트노드와 $c$가 포함된 셋의 루트노드가 $a$로 서로 같습니다. 이대로 연산을 마칩니다. 다음과 같습니다.

• {$a,b,c,d$}, {$e,f,g$}, {$h,i$}, {$j$}

이렇게 만든 연결요소가 있고, 임의의 노드 $u$와 $v$가 같은 연결요소 내에 있는지 여부를 가려내려면 다음과 같이 수행합니다.

• find(u)와 find(v)가 같은 결과이면 True
• 그렇지 않으면 False