Strongly Connected Components(SCC) 는 방향 그래프에서 매우 중요한 구조입니다. 하나의 SCC 안에 있는 모든 정점은 다른 모든 정점으로 도달할 수 있고, 반대 방향으로도 다시 돌아올 수 있습니다.

두 정점 u, v가 같은 SCC에 있다면 다음이 모두 성립해야 합니다.

u ~> v
v ~> u

Reachability와 Strong Connectivity의 차이

다음 그래프를 보겠습니다.

A -> B -> C

A에서 C로 갈 수 있지만 C에서 A로 돌아갈 수 있다는 보장은 없습니다. 따라서 두 정점이 같은 SCC라고 할 수 없습니다.

반면:

A -> B -> C
^         |
|_________|

에서는 모든 정점이 서로 도달 가능하므로 {A, B, C}가 하나의 SCC입니다.

SCC는 어디에 쓰이나요?

• 소프트웨어 모듈의 Circular Dependency 탐지
• Microservice 의존성 분석
• Call Graph와 Control-Flow Graph 분석
• 방향성을 가진 소셜 네트워크 분석
• State Machine의 반복 가능한 상태 그룹 탐지
• Build System 및 Package Manager의 dependency 분석
• 큰 방향 그래프를 더 작은 DAG로 압축

Kosaraju와 Tarjan

대표적인 SCC 알고리즘은 다음 두 가지입니다.

1. Kosaraju
2. Tarjan

둘 다 시간 복잡도는:

O(V + E)

입니다.

Kosaraju는 두 번의 DFS와 역방향 그래프를 사용하므로 개념적으로 이해하기 쉽습니다.

Kosaraju 알고리즘의 동작

1. 원본 그래프에서 DFS를 수행하고 정점의 종료 순서를 저장합니다.
2. 모든 간선의 방향을 반대로 뒤집습니다.
3. 종료 시간이 큰 정점부터 역방향 그래프에서 DFS를 수행합니다.

세 번째 단계에서 시작되는 각각의 DFS가 하나의 SCC를 만듭니다.

왜 동작하나요?

각 SCC를 하나의 super-node로 압축하면 Condensation Graph가 만들어집니다. 이 그래프는 항상 DAG입니다.

만약 압축된 그래프에 cycle이 있다면, 그 cycle에 포함된 SCC들은 서로 도달할 수 있다는 뜻이므로 원래부터 하나의 더 큰 SCC여야 합니다.

첫 번째 DFS의 finishing order와 간선 반전은 두 번째 DFS가 각 SCC를 분리해서 방문할 수 있게 합니다.

JavaScript 구현

function kosaraju(graph) {
  const visited = new Set();
  const order = [];
  const nodes = new Set(Object.keys(graph));

  for (const neighbors of Object.values(graph)) {
    for (const node of neighbors) nodes.add(node);
  }

  function dfs1(node) {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) dfs1(next);
    }

    order.push(node);
  }

  for (const node of nodes) {
    if (!visited.has(node)) dfs1(node);
  }

  const reversed = {};

  for (const node of nodes) reversed[node] = [];

  for (const [from, neighbors] of Object.entries(graph)) {
    for (const to of neighbors) reversed[to].push(from);
  }

  visited.clear();
  const components = [];

  function dfs2(node, component) {
    visited.add(node);
    component.push(node);

    for (const next of reversed[node] ?? []) {
      if (!visited.has(next)) dfs2(next, component);
    }
  }

  while (order.length) {
    const node = order.pop();

    if (!visited.has(node)) {
      const component = [];
      dfs2(node, component);
      components.push(component);
    }
  }

  return components;
}

실무 예시: 순환 의존성

Auth -> User
User -> Payment
Payment -> Auth

이 세 모듈은 순환 의존성을 형성하며 SCC 분석을 통해 하나의 강하게 연결된 그룹으로 탐지할 수 있습니다.

Condensation Graph

예를 들어:

S1 = {A, B, C}
S2 = {D, E}
S3 = {F}

를 각각 하나의 노드로 압축하면:

S1 -> S2 -> S3

와 같은 DAG를 만들 수 있습니다. 이는 scheduling, dependency analysis, 후속 그래프 처리에 유용합니다.

복잡도

Time:  O(V + E)
Space: O(V + E)

모든 정점과 간선을 상수 횟수만큼 처리하기 때문입니다.

중요한 Edge Case

• 고립된 정점 하나도 SCC입니다.
• Self-loop가 있는 정점도 단일 SCC가 될 수 있습니다.
• 전체 그래프가 strongly connected라면 SCC는 하나뿐입니다.
• DAG에서는 모든 정점이 각각 하나의 SCC입니다.

SCC와 Cycle Detection의 차이

정점이 둘 이상인 SCC에는 반드시 cycle이 존재합니다. 하지만 SCC는 단순히 cycle 하나를 찾는 것이 아니라 전체 그래프를 최대 mutual-reachability 영역으로 분할합니다.

언제 사용해야 하나요?

다음과 같은 질문에 적합합니다.

• 어떤 정점들이 서로 양방향으로 도달 가능한가?
• 어떤 dependency들이 순환 구조를 만드는가?
• 어떤 서비스나 모듈이 강하게 결합되어 있는가?
• 방향 그래프를 어떻게 DAG로 압축할 수 있는가?
• 어떤 상태들이 반복 가능한 영역을 형성하는가?

정리

Kosaraju는 다음 흐름으로 기억할 수 있습니다.

DFS + finishing order
        ↓
Reverse graph
        ↓
DFS in reverse finishing order
        ↓
SCCs

핵심은 코드를 외우는 것이 아니라 mutual reachability, finishing time, condensation graph가 서로 어떻게 연결되는지 이해하는 것입니다.