그래프 이론: 강한 연결 요소들(SCC)

이 글의 목차

인터랙티브

타잔은 서로 도달 가능한 정점을 SCC로 묶는다

다음 SCC자동초기화

방향 그래프

다음 SCC를 눌러 첫 성분을 드러내세요.

SCC를 접으면 방향 비순환 그래프(DAG)가 된다

타잔 알고리즘으로 찾는 강한 연결 요소

방향 그래프에서 두 정점이 서로 도달할 수 있으면 서로 강하게 연결되어 있다고 합니다. **강한 연결 요소(SCC)**는 이 상호 도달 성질을 만족하는 정점들의 최대 집합입니다. 각 SCC를 하나의 정점으로 합치면 방향 비순환 그래프가 되어 의존 관계나 도달성을 분석하는 데 활용할 수 있습니다.

타잔 알고리즘의 한 번 탐색

타잔 알고리즘은 깊이 우선 탐색(DFS) 한 번으로 모든 SCC를 O(V + E) 시간에 찾습니다. 정점 v의 index[v]는 발견 순서 번호입니다. lowLink[v]는 DFS 트리 간선을 따라가고, 마지막에 아직 활성 스택에 있는 정점으로 간선을 최대 한 번 따라갔을 때 도달할 수 있는 가장 작은 발견 번호입니다.

DFS 트리 자식의 탐색이 끝나면 부모는 자식의 lowLink를 반영합니다. 아직 스택에 있는 정점으로 향하는 간선은 그 정점의 index를 사용하고, 이미 스택에서 빠진 정점으로 향하는 간선은 무시합니다. 여기서 활성 스택은 재귀 호출 스택과 다릅니다. SCC가 완성되지 않은 정점을 보관합니다.

lowLink[v] === index[v]이면 v의 DFS 하위 트리에서 도달 가능한 정점은 더 앞선 활성 정점으로 돌아갈 수 없습니다. 따라서 v는 SCC의 루트이고, 활성 스택에서 v까지 꺼낸 정점들이 정확히 그 요소를 이룹니다. 바깥 반복문은 아직 방문하지 않은 정점에서도 탐색을 시작하므로 서로 연결되지 않은 부분도 처리합니다.

JavaScript 구현

함수는 인접 리스트 graph를 받습니다. graph[u]에는 u에서 나가는 간선의 도착점인 0부터 시작하는 인덱스를 나열합니다. 모든 도착점이 유효한 인덱스라고 가정합니다. 반환값은 0부터 시작하는 정점 인덱스 배열들의 목록이며, 요소와 각 요소 안의 순서는 정해져 있지 않습니다.

function stronglyConnectedComponents(graph) {
  const n = graph.length;
  const index = Array(n).fill(-1);
  const lowLink = Array(n).fill(0);
  const onStack = Array(n).fill(false);
  const stack = [];
  const components = [];
  let nextIndex = 0;

  function visit(v) {
    index[v] = nextIndex;
    lowLink[v] = nextIndex;
    nextIndex += 1;
    stack.push(v);
    onStack[v] = true;

    for (const w of graph[v]) {
      if (index[w] === -1) {
        visit(w);
        lowLink[v] = Math.min(lowLink[v], lowLink[w]);
      } else if (onStack[w]) {
        lowLink[v] = Math.min(lowLink[v], index[w]);
      }
    }

    if (lowLink[v] === index[v]) {
      const component = [];
      let w;
      do {
        w = stack.pop();
        onStack[w] = false;
        component.push(w);
      } while (w !== v);
      components.push(component);
    }
  }

  for (let v = 0; v < n; v += 1) {
    if (index[v] === -1) visit(v);
  }

  return components;
}

간선이 0→1, 1→2, 2→0, 2→3, 3→4, 4→3, 4→5인 그래프의 결과는 {0,1,2}, {3,4}, {5}입니다(순서는 달라도 됩니다). 앞의 세 정점은 하나의 순환을 이루고, 3과 4도 서로 순환하며, 5에서는 도달할 수 있고 다시 돌아오는 정점이 없습니다.

시간 복잡도는 O(V + E), 보조 공간 복잡도는 O(V)입니다. 이 구현은 재귀를 사용하므로 호출 깊이가 O(V)까지 늘 수 있습니다. 정점 수가 매우 많거나 깊은 그래프에서는 JavaScript 실행 환경의 호출 스택 한도를 넘을 수 있으므로 반복형 DFS를 고려하세요.

핵심: 발견 번호는 탐색 순서를, low-link는 도달 가능한 가장 앞선 활성 정점을 나타냅니다. low-link가 루트의 발견 번호와 같아지는 순간 SCC 하나를 꺼냅니다.