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

concept

방향그래프(Directed Graph)의 연결요소(connected component) 내 노드 $u$에서 $v$로 향하는 경로와 $v$에서 $u$로의 경로가 존재한다면 해당 연결요소를 강연결요소라고 합니다. 예컨대 다음 그림에서는 총 네 개의 강연결요소가 있습니다. 그래프가 주어졌을 때 해당 그래프의 강연결요소를 찾아내는 것이 이 글의 목적입니다.

강연결요소를 찾아내는 기법의 핵심 아이디어는 다음 그림과 같습니다. 원그래프 $G$의 노드 $a$에서 $b$로 향하는 경로가 있습니다. 그런데 엣지 방향을 정반대로 바꾼 $G^T$를 분석해본 결과도 역시 $a$에서 $b$로 갈 수 있다(다이렉트로 가지 못하고 여러 노드를 거쳐 가더라도 관계 없음)고 칩시다. 그렇다면 $a$와 $b$ 사이에는 사이클(cycle)이 있어 강연결요소 속성을 만족한다는 것입니다.

algorithm

강연결요소는 깊이우선탐색(Depth First Search)을 기본으로 해서 구합니다. 우선 주어진 그래프에 대해 DFS를 적용합니다. 다음과 같습니다. 아래 예제 그래프의 경우 노드 안에 적혀진 숫자가 각각 DFS 알고리즘의 start time, finish time이 됩니다(음영처리로 클러스터를 표시한 부분은 일단 무시).

이후 다음 두 가지 작업을 수행합니다.

• 그래프를 transpose한다. 다시 말해 노드는 그대로 놔두고 엣지 방향만 바꾼다. (인접행렬을 transpose한다는 의미)
• transpse한 그래프를 대상으로 DFS를 한번 더 수행한다. 기존 적용한 DFS의 finish time을 내림차순 정렬해 그 순서대로 DFS를 수행한다.

이 점 염두에 두고 다음 그림을 보겠습니다. 주어진 그래프를 transpose했으므로 엣지 방향이 위 그림과 반대임을 확인할 수 있습니다. finish time 기준 내림차순으로 DFS를 수행하므로, finish time이 16으로 가장 큰 $b$가 첫번째 대상입니다. $e$까지 순회하면 더 이상 방문할 노드가 없으므로 미방문 노드들 가운데 finish time이 9로 가장 큰 $d$를 대상으로 순회합니다. 마찬가지로 $g$와 $h$에 대해서도 같은 방식으로 각각 수행해주면 DFS가 끝납니다.

이 결과를 기존 그래프에 DFS를 수행한 것과 비교합니다. 여기서 두 결과 모두 서로 도달 가능한 노드들을 클러스터한 것이 음영처리된 부분입니다.

강연결요소끼리는 어떤 방향에서든 서로 도달가능하기 때문에 다음과 같이 그래프 정보를 압축하는 데 요긴하게 쓰일 수 있습니다.