강한 연결 요소: 방향 그래프 안에서 서로 돌아갈 수 있는 그룹
방향 그래프에서 두 정점 사이에 양방향으로 각각 경로가 있으면 서로 강하게 연결되어 있다. 이런 상호 도달 관계로 묶인 최대 정점 집합을 강한 연결 요소, SCC라고 한다. 단일 간선이 양방향이라는 뜻이 아니라 여러 간선을 거친 경로로 돌아올 수 있다는 뜻이다.
각 요소 내부에서는 서로 도달할 수 있지만 두 요소 사이에는 역방향 경로가 없다.
사이클 하나와도 완전히 같지는 않다
A→B→C→A는 하나의 SCC다. 여기에 C→D만 있고 D에서 돌아오는 경로가 없으면 D는 다른 요소다. 여러 사이클이 정점을 공유하거나 왕복 경로로 연결되어 더 큰 SCC가 될 수도 있다. 고립 정점도 자신만의 요소로 취급한다.
각 SCC를 한 정점으로 축약하면 요소 사이 그래프는 DAG가 된다. 축약 그래프에 사이클이 있다면 그 요소들 사이에 모두 왕복 경로가 생겨 처음부터 하나의 SCC여야 하기 때문이다. 복잡한 방향 관계를 순서 있는 큰 덩어리로 바꿀 수 있다.
두 번의 DFS를 사용하는 Kosaraju 관점
첫 번째 DFS는 각 정점의 처리가 끝나는 시각을 기록한다. 모든 간선 방향을 뒤집은 전치 그래프에서, 종료 시각이 큰 정점부터 다시 DFS를 시작하면 각 탐색에서 하나의 요소를 얻는다.
finish_order = empty list
for each vertex in original_graph:
if vertex is unseen:
DFS original_graph from vertex
append vertices when their DFS finishes
reverse_graph = reverse every directed edge
clear visited state
for vertex in reverse(finish_order):
if vertex is unseen:
component = DFS reverse_graph from vertex
record component as one SCC
중요한 것은 첫 DFS의 발견 순서가 아니라 종료 순서다. 그 순서가 축약 DAG의 간선 방향과 맞물려 두 번째 탐색이 아직 미방문인 다른 요소로 넘어가지 않도록 한다. 방향을 뒤집는 작업과 방문 기록 초기화도 빠뜨릴 수 없다.
인접 리스트에서 두 번의 DFS와 전치 그래프 생성은 O(V+E), 저장 공간도 O(V+E)다. Tarjan 알고리즘은 발견 번호, low-link, 스택을 이용해 한 번의 DFS로 요소를 얻지만 스택에 남아 있는 상태의 의미를 정확히 관리해야 한다.
웹페이지 링크, 패키지 의존성, 제어 흐름을 분석할 때 서로 순환하는 그룹을 식별할 수 있다. 요소 단위로 묶으면 밖으로 향하는 관계를 따로 처리하기 쉬워진다. “출발점에서 모두 갈 수 있다”만으로 강한 연결이라고 판단하면 돌아오는 경로를 놓친다.
무방향 그래프의 연결 요소와도 다르다. 방향을 무시하면 A→B만 있어도 함께 묶이지만 SCC에서는 반대 경로가 없으면 분리된다. 분석 목적에 맞춰 강한 연결과 약한 연결의 기준을 먼저 정해야 한다.
요소 번호는 분류를 위한 표식이며 원래 정점의 이름이나 우선순위가 아니다.