강한 연결 요소

수치해석 소프트웨어 마지막 수정: 2026-08-28 04:14:27

1. 개요[편집]

강한 연결 요소 Strongly connected component, SCC
대상	유향그래프 $G=(V,E)$
정의	서로 도달 가능한 정점들의 극대 집합
대표 알고리즘	타잔(1972) · 코사라주-샤리르(1978/81) · 경로 기반(Gabow)
복잡도	셋 다 $\Theta(V+E)$
DFS 횟수	타잔·경로기반 1회 / 코사라주 2회 + 역그래프
핵심 성질	축약 그래프는 항상 DAG
수치해석 용도	희소행렬 블록 삼각화(BTF) · DAE 대수루프 탐지

강한 연결 요소(strongly connected component, SCC)는 유향그래프에서 « $u$ 에서 $v$ 로 가는 경로와 $v$ 에서 $u$ 로 가는 경로가 둘 다 존재한다»는 관계로 정점을 묶었을 때 나오는 극대 정점집합이다. “왕복 가능”이라는 관계가 반사·대칭·이행적인 동치관계이므로, SCC 들은 $V$ 를 빈틈없이 겹침 없이 분할한다. 극대라는 조건이 붙는 이유는 그것 없이는 정점 하나짜리 집합도 조건을 만족해 버려서 정의가 무의미해지기 때문이다.

이 개념이 한 줄짜리 정의에 비해 과분한 대접을 받는 이유는 딱 하나다. SCC 를 하나의 점으로 뭉개면 남는 그래프가 반드시 사이클 없는 유향그래프(DAG)가 된다. 즉 임의의 유향그래프는 “사이클 덩어리 + 그 덩어리들 사이의 방향 순서”로 정확히 두 층으로 분해된다. 사이클이 있으면 위상 정렬도, 역위상 순서 동적 계획법도, 소거 순서 결정도 전부 막히는데, SCC 축약이 그 막힘을 딱 사이클 안쪽으로만 가둬 준다. 이행 폐포를 SCC 로 먼저 줄이는 것도, 2-SAT 이 선형 시간에 풀리는 것도, 희소 연립방정식이 작은 블록들로 쪼개지는 것도 전부 이 한 문장의 따름정리다.

2. 축약 그래프가 DAG 인 이유[편집]

정점 $v$ 가 속한 SCC 를 $C(v)$ 라 하고, $C(u) \ne C(v)$ 이면서 $G$ 에 $u \to v$ 간선이 있을 때 $C(u) \to C(v)$ 간선을 놓은 그래프를 축약 그래프(condensation) $G^{\mathrm{SCC}}$ 라 부른다.

증명은 세 줄이다. $G^{\mathrm{SCC}}$ 에 사이클 $C_1 \to C_2 \to \cdots \to C_k \to C_1$ 이 있다고 하자. 그러면 $C_1$ 의 아무 정점에서 $C_2$ 의 아무 정점으로 갈 수 있고(각 $C_i$ 내부는 강하게 연결돼 있으므로 대표 정점을 어떻게 잡든 상관없다) 한 바퀴 돌아 돌아올 수 있다. 즉 $C_1 \cup \cdots \cup C_k$ 전체가 서로 왕복 가능하므로 하나의 SCC 여야 한다 — $C_i$ 들이 극대라는 가정에 모순이다. 그러므로 사이클은 없다. $\blacksquare$

여기서 파생되는 실무용 어휘 몇 개를 정리해 두면 나중에 편하다.

소스 SCC — 진입차수 0. 밖에서 아무도 도달할 수 없다.
싱크 SCC(closed component) — 진출차수 0. 한번 들어가면 못 나온다. 마르코프 연쇄(마르코프 연쇄 몬테카를로의 그 연쇄)로 읽으면 재귀(recurrent) 클래스가 정확히 이것이고, 그래프 전체가 하나의 SCC 라는 것이 곧 기약성(irreducibility)이다. 정상분포의 유일성 논의가 여기서 시작한다.
자명한 SCC — 크기 1 이고 자기 루프도 없는 것. $R^{+}$ 와 $R^{*}$ 를 가르는 유일한 경우라 이행 폐포 쪽에서 늘 발목을 잡는다.

3. 타잔 알고리즘[편집]

로버트 타잔이 1972년에 낸 것으로, DFS 한 번에 끝난다.¹ 정점마다 방문 번호 num[v](DFS 에서 몇 번째로 발견됐나)와 low[v](현재 DFS 스택에 살아 있는 정점 중 $v$ 의 부분트리에서 도달 가능한 최소 번호)를 들고 다닌다.

index = 0; S = empty stack
dfs(v):
  num[v] = low[v] = index++;  S.push(v);  onstack[v] = true
  for each edge v -> w:
      if w is unvisited:
          dfs(w);  low[v] = min(low[v], low[w])
      else if onstack[w]:                 # 이 조건이 전부다
          low[v] = min(low[v], num[w])
  if low[v] == num[v]:                     # v 가 SCC 의 뿌리
      pop S until v is popped -> 하나의 SCC

low[v] == num[v] 는 ” $v$ 의 부분트리에서 $v$ 보다 먼저 발견된 살아 있는 정점으로 되돌아가는 길이 없다”는 뜻이고, 그 순간 스택에서 $v$ 위에 쌓인 것들이 정확히 $v$ 를 뿌리로 하는 SCC 다.

onstack[w] 검사를 빼먹는 것이 이 알고리즘 최대의 함정이다. 이미 처리가 끝나 다른 SCC 로 확정된 정점 $w$ 로 가는 간선(교차 간선)까지 low 갱신에 반영하면, 서로 왕복 불가능한 덩어리들이 한 SCC 로 뭉쳐 버린다. 무향그래프의 단절점·다리 찾기 코드에서 low 를 베껴 오면 이 검사가 없어서 조용히 틀린 답이 나온다.

부수효과 하나가 실전에서 대단히 유용하다. 타잔은 SCC 를 축약 그래프의 역위상 순서로 뱉는다. 싱크가 먼저, 소스가 마지막이다. 그래서 도달집합 누적이나 2-SAT 해 구성처럼 “역위상 순서로 훑어야 하는” 작업은 SCC 배열을 그냥 나온 순서대로 쓰면 되고, 별도의 위상 정렬 패스가 필요 없다.

남은 실무 문제는 재귀 깊이다. 정점 100만 개짜리 호출 그래프나 회로 넷리스트에 이 코드를 재귀로 돌리면 스택 오버플로가 국룰이라, 프로덕션 구현은 대개 명시적 스택으로 펼쳐 쓴다.

4. 코사라주 알고리즘[편집]

코사라주(1978, 미출판)와 샤리르(1981)에게 각각 돌아가는 두 번 DFS 방식이다.

$G$ 에서 DFS 를 돌려 종료 시각 내림차순으로 정점을 쌓는다.
역그래프 $G^{\mathsf{T}}$ 에서 그 순서대로 DFS 를 돌린다. 각 DFS 트리 하나가 SCC 하나다.

증명의 핵심은 “종료 시각이 가장 늦은 정점은 $G^{\mathrm{SCC}}$ 의 소스 SCC 에 속한다”는 보조정리이고, $G^{\mathsf{T}}$ 에서 소스는 싱크가 되므로 두 번째 DFS 가 딱 그 SCC 만 긁어 오게 된다. 결과가 나오는 순서는 타잔과 반대로 축약 그래프의 위상 순서다.

두 알고리즘의 대비는 이렇게 갈린다.

	타잔	코사라주
DFS 횟수	1	2
역그래프	필요 없음	필요
추가 배열	num, low, onstack, 스택	종료순서 배열, 방문표시
출력 순서	역위상	위상
설명 난이도	증명이 좀 뻑뻑함	칠판에 그리면 바로 납득

점근 복잡도는 둘 다 $\Theta(V+E)$ 이고 실측도 몇 배 안에서 논다. 그럼에도 대규모 데이터에서는 타잔이 이기는 편인데, 이유가 재미있다. 역그래프를 만드는 비용이 사실상 희소행렬의 CSR↔CSC 변환이라, $E$ 개 간선을 한 번 더 저장하고 정렬해야 하기 때문이다. 인접행렬을 이미 CSR·CSC 양쪽으로 들고 있는 코드베이스라면 이 부담이 사라지고, 그때는 코사라주가 캐시 친화적이라 오히려 유리해지기도 한다.

세 번째 갈래로 경로 기반(path-based) 알고리즘이 있다. 퍼덤(1970)·먼로(1971)·데이크스트라(1976)를 거쳐 개보우가 다듬은 형태로, low 배열 없이 스택 두 개(정점 스택과 경계 스택)만으로 같은 일을 한다. DFS 한 번인 것은 타잔과 같은데, 증명이 “현재 DFS 경로 위에서 아직 확정 안 된 덩어리들의 경계”라는 그림 하나로 끝나서 교육용으로 선호된다.

5. 왜 시뮬레이션 하는 사람이 이걸 아는가[편집]

5.1. 희소행렬 블록 삼각화[편집]

$n \times n$ 희소행렬 $A$ 로 $Ax=b$ 를 푼다고 하자. 행렬을 그래프로 읽는 방법은 하나뿐이다 — 정점 $i$ , 그리고 $a_{ij} \ne 0$ 일 때 간선 $i \to j$ . 이때 SCC 를 구해 같은 SCC 끼리 인접하게 대칭 치환 $P A P^{\mathsf{T}}$ 를 걸면 행렬이 블록 삼각형이 된다. 축약 그래프가 DAG 이므로 블록들 사이에는 방향 순서가 있고, 그 순서가 곧 위상 정렬이다.

P A P^{\mathsf{T}} \;=\; \begin{pmatrix} A_{11} & A_{12} & \cdots & A_{1k} \\ & A_{22} & \cdots & A_{2k} \\ & & \ddots & \vdots \\ & & & A_{kk} \end{pmatrix}

이러면 LU 분해를 전체에 걸 필요가 없다. 대각 블록만 인수분해하고 블록 사이는 후진대입으로 넘기면 되므로, 비용이 대략 $O(n^3)$ 짜리 한 번에서 $\sum_i O(n_i^3)$ 로 떨어지고 충전(fill-in)도 대각 블록 안에 갇힌다. 블록 하나가 전체 크기라면 아무 이득이 없고, 블록이 잘게 갈릴수록 이득이 커진다.²

앞 단계가 하나 더 있다. 대각선에 0 이 있으면 위 그래프 해석이 깨지므로, 먼저 이분 매칭으로 최대 횡단(maximum transversal)을 찾아 행을 치환해 대각선을 0 이 아니게 만든다. 매칭 + SCC 로 이루어진 이 2단 절차가 Dulmage-Mendelsohn 분해이고, MATLAB 의 dmperm 과 SuiteSparse 의 BTF 모듈이 하는 일이 이것이다. 구조적으로 특이한(또는 직사각) 행렬에서는 매칭 단계가 수평·정방·수직 블록으로 나누는 조(coarse) 분해까지 담당하고, SCC 는 그 정방 블록을 잘게 쪼개는 세(fine) 분해를 맡는다.

단, 만능은 아니다. 유한요소법이나 유한체적법으로 이산화한 PDE 행렬은 격자가 연결돼 있는 한 통째로 하나의 SCC 라서 BTF 가 아무것도 못 준다. 반면 회로 방정식(SPICE), 화학 공정 플로시트, 경제 투입산출 모형처럼 인과의 방향이 있는 계에서는 블록 수가 수백~수천 개로 갈라져서 효과가 극적이다. “블록 삼각화가 안 먹히는 것은 그 계가 원래 한 덩어리로 커플링돼 있다는 진단”이라고 읽으면 된다.

5.2. DAE 와 대수 루프[편집]

미분대수방정식 기반 모델링 언어(Modelica 계열)와 모듈러 공동 시뮬레이션은 컴파일 단계에서 방정식-미지수 이분 매칭 → SCC → 블록 하삼각(BLT) 정렬을 돌린다. 결과 블록 중 크기 1 짜리는 대입 한 번으로 풀리고, 크기 2 이상인 블록이 곧 대수 루프다. 즉 “이 모델에 대수 루프가 있습니다”라는 그 짜증나는 경고문의 실체는 SCC 알고리즘이 크기 2 이상 성분을 발견했다는 보고다. 루프 안쪽은 뉴턴 반복(준-뉴턴법 포함)으로 따로 풀 수밖에 없으므로, 블록 크기가 곧 모델링의 비용이다.

5.3. 반응 네트워크와 의존성 그래프[편집]

화학반응 메커니즘을 종(species)을 정점, “A 가 B 의 생성에 유의하게 기여함”을 간선으로 놓으면 유향그래프가 되고, 메커니즘 축소의 DRG(directed relation graph) 계열 기법이 이 위에서 도달성을 따진다. 강하게 연결된 종 집합은 함께 살거나 함께 죽는 그룹이라 개별로 잘라낼 수 없다. 자기촉매 사이클 탐지도 같은 도구다.

소프트웨어 쪽 응용도 결국 같은 그림이다. 모듈 의존성의 순환 참조, 빌드 타깃의 사이클, 상호 재귀 함수 묶기(컴파일러는 호출 그래프의 SCC 단위로 타입 추론 순서를 정한다), 스프레드시트의 순환 참조 경고 — 전부 “사이클이 있으면 위상 정렬이 안 되니 사이클 덩어리를 먼저 찾자”의 변주다.³

6. 관련 문서[편집]

Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms”. SIAM J. Comput. 1(2), 146–160. 이 한 편에 SCC 뿐 아니라 무향그래프의 이중연결 성분과 단절점까지 들어 있다. DFS 라는 뻔한 것에 번호 두 개를 붙였더니 논문 한 편이 나온 셈인데, 이후 40년간 “일단 low 를 정의해 보자”가 그래프 알고리즘 논문의 국룰이 됐다. ↩
사족이지만 이 이득은 치환을 미리 알아야 얻는 것이고, SCC 계산 자체는 값이 아니라 0/1 패턴만 보는 기호적(symbolic) 단계다. 그래서 시간 적분 중에 값만 바뀌고 희소 패턴이 그대로인 문제라면 BTF 를 한 번만 구해 놓고 수천 스텝을 우려먹을 수 있다. 반대로 적응 격자처럼 패턴이 매 스텝 바뀌면 기호 단계가 매번 되살아나 생각보다 비싸진다. ↩
순환 참조 경고가 뜨는 순간 사람들이 제일 먼저 하는 일은 “어디가 순환인지” 찾는 것인데, 좋은 도구는 SCC 를 통째로 보여 주고 나쁜 도구는 간선 하나만 짚어 준다. 사이클은 간선 하나의 죄가 아니라 덩어리의 성질이므로, “이 import 를 지우세요”는 대개 틀린 조언이다. 지워야 할 간선을 최소로 고르는 문제는 최소 피드백 간선 집합이고 그건 NP-완전이다. 도구가 답을 안 주는 데는 이유가 있었다. ↩