강한 연결 요소 (strongly connected components (SCC))
쉽게 풀면
강한 연결 요소는 방향 그래프 안에서 '서로가 서로에게 도달할 수 있는' 정점들의 묶음이다. 예를 들어 A에서 B로 가는 길도 있고 B에서 A로 돌아오는 길도 있다면, A와 B는 같은 강한 연결 요소에 속한다. 큰 방향 그래프를 이런 강한 연결 요소 단위로 압축하면, 요소들 사이의 관계는 사이클 없는 방향 그래프(DAG)가 되어 훨씬 다루기 쉬워진다. 타잔 알고리즘이나 코사라주 알고리즘 등을 이용해 깊이 우선 탐색 기반으로 구할 수 있다.
왜 중요한가
강한 연결 요소를 찾아내는 것은 복잡한 방향 그래프를 순환 없는 구조로 압축해 분석을 단순화하는 기본 전처리 단계이기 때문에, 소프트웨어 모듈 간 순환 의존성 탐지, 소셜 네트워크나 웹 링크 구조 분석, 회로 설계 검증 등 여러 분야의 그래프 알고리즘 논문에서 널리 활용됩니다. 큰 그래프를 강한 연결 요소 단위로 요약하면 이후 위상 정렬이나 최단 경로 같은 다른 알고리즘을 적용하기가 훨씬 쉬워진다는 점도 이 개념이 자주 언급되는 이유입니다.
논문에서는 이렇게 쓰입니다
방향 그래프를 요약하거나 순환 의존 관계를 찾아낼 때 사용하는 그래프 분석 기법으로 인용된다.
소프트웨어 공학 연구에서는 강한 연결 요소를 이용해 서로 얽혀 있어 분리하기 어려운 코드 모듈 묶음을 찾아내는 데 활용한다는 뜻이다.
데이터베이스 시스템 연구에서는 자원을 기다리는 관계를 그래프로 표현했을 때 강한 연결 요소가 나타나면 서로가 서로를 막고 있는 교착 상태임을 뜻한다는 것을 보여준다.
조금 더 깊게 보면
강한 연결 요소를 구하는 대표적인 방법으로는 두 번의 깊이 우선 탐색을 이용하는 코사라주 알고리즘과, 한 번의 탐색만으로 저점 링크(low-link) 값을 계산해 구하는 타잔 알고리즘이 있으며, 둘 다 정점과 간선 수에 대해 선형에 가까운 시간에 동작합니다. 강한 연결 요소별로 그래프를 압축한 뒤 얻어지는 요소 그래프(condensation graph)는 항상 사이클이 없는 방향 그래프(DAG)가 되므로, 이후 위상 정렬 같은 DAG 전용 알고리즘을 적용할 수 있게 됩니다.
주의할 점
강한 연결 요소는 방향 그래프에서만 의미가 있는 개념이며, 무방향 그래프에서는 단순 연결 요소(connected component) 개념을 대신 사용한다.