강한 연결 요소(SCC) — 코사라주와 타잔 알고리즘

지난 글에서 무방향 그래프의 MST를 구하는 프림을 배웠습니다. 이번에는 방향 그래프(Directed Graph) 에서 핵심 구조인 강한 연결 요소(SCC, Strongly Connected Component)를 찾는 알고리즘을 다룹니다. SCC는 서로 양방향으로 도달 가능한 노드들의 최대 집합입니다. 웹 페이지 링크 분석, 컴파일러의 순환 의존성 탐지, 게임 맵의 폐쇄 구역 분석 등에 활용됩니다.

SCC란?

방향 그래프에서 두 노드 u, v가 u → v 경로와 v → u 경로가 모두 존재할 때 같은 SCC에 속합니다.

모든 SCC를 하나의 노드로 축소하면 압축 그래프(Condensation Graph)가 만들어지는데, 이는 항상 DAG(사이클 없는 방향 그래프)입니다.

코사라주(Kosaraju) 알고리즘

가장 직관적인 방법입니다.

1. 1단계: 원래 그래프에서 DFS 수행, 노드 종료 순서를 스택에 기록
2. 2단계: 그래프의 역방향(transpose) 에서 스택에서 꺼내는 순서대로 DFS — 각 DFS가 탐색하는 노드가 하나의 SCC

from collections import defaultdict

def kosaraju(n, adj):
    # 역방향 그래프 구성
    radj = defaultdict(list)
    for u in adj:
        for v in adj[u]:
            radj[v].append(u)

    # 1단계: 종료 순서 스택
    visited = [False] * n
    order = []

    def dfs1(v):
        visited[v] = True
        for w in adj[v]:
            if not visited[w]:
                dfs1(w)
        order.append(v)

    for v in range(n):
        if not visited[v]:
            dfs1(v)

    # 2단계: 역방향 그래프 DFS
    visited2 = [False] * n
    sccs = []

    def dfs2(v, comp):
        visited2[v] = True
        comp.append(v)
        for w in radj[v]:
            if not visited2[w]:
                dfs2(w, comp)

    for v in reversed(order):
        if not visited2[v]:
            comp = []
            dfs2(v, comp)
            sccs.append(comp)

    return sccs

타잔(Tarjan) 알고리즘

DFS 한 번으로 SCC를 모두 찾습니다. 각 노드에 disc(발견 시각)와 low(도달 가능한 최소 disc)를 부여하고, low[u] == disc[u]이면 u가 SCC의 루트입니다.

def tarjan(n, graph):
    disc = [-1] * n
    low = [-1] * n
    on_stack = [False] * n
    stack = []
    timer = [0]
    sccs = []

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        stack.append(u)
        on_stack[u] = True

        for v in graph[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], disc[v])

        # SCC 루트: low[u] == disc[u]
        if low[u] == disc[u]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == u:
                    break
            sccs.append(scc)

    for v in range(n):
        if disc[v] == -1:
            dfs(v)

    return sccs

재귀 깊이 문제 해결 — 반복 타잔

Python의 기본 재귀 한도(1000)를 초과하는 큰 그래프에서는 반복 버전이 필요합니다.

import sys
sys.setrecursionlimit(10 ** 6)  # 간단한 해결책

# 또는 반복 DFS로 타잔 구현
def tarjan_iterative(n, graph):
    disc = [-1] * n
    low = [-1] * n
    on_stack = [False] * n
    stack = []
    timer = [0]
    sccs = []
    call_stack = []

    for start in range(n):
        if disc[start] != -1:
            continue
        call_stack.append((start, iter(graph[start])))
        disc[start] = low[start] = timer[0]
        timer[0] += 1
        stack.append(start)
        on_stack[start] = True

        while call_stack:
            u, neighbors = call_stack[-1]
            try:
                v = next(neighbors)
                if disc[v] == -1:
                    disc[v] = low[v] = timer[0]
                    timer[0] += 1
                    stack.append(v)
                    on_stack[v] = True
                    call_stack.append((v, iter(graph[v])))
                elif on_stack[v]:
                    low[u] = min(low[u], disc[v])
            except StopIteration:
                call_stack.pop()
                if call_stack:
                    parent = call_stack[-1][0]
                    low[parent] = min(low[parent], low[u])
                if low[u] == disc[u]:
                    scc = []
                    while True:
                        w = stack.pop()
                        on_stack[w] = False
                        scc.append(w)
                        if w == u:
                            break
                    sccs.append(scc)
    return sccs

활용 — 2-SAT

SCC의 대표적인 응용은 2-SAT(2-Satisfiability Problem)입니다. 각 리터럴 xi와 ¬xi를 노드로 만들고 논리 함의 관계를 간선으로 표현한 뒤, xi와 ¬xi가 같은 SCC에 있으면 UNSAT입니다.

def two_sat(n, clauses):
    """
    n개 변수, clauses: [(a, b)] where a or b = True
    변수 i: 노드 2i, 변수 ¬i: 노드 2i+1
    """
    graph = defaultdict(list)
    for a, b in clauses:
        # (a or b) == (¬a → b) and (¬b → a)
        graph[a ^ 1].append(b)
        graph[b ^ 1].append(a)

    sccs = tarjan(2 * n, graph)
    comp = [0] * (2 * n)
    for i, scc in enumerate(sccs):
        for v in scc:
            comp[v] = i

    for i in range(n):
        if comp[2 * i] == comp[2 * i + 1]:
            return None  # UNSAT
    return [comp[2 * i] > comp[2 * i + 1] for i in range(n)]

알고리즘 비교

특성	코사라주	타잔
DFS 횟수	2회	1회
시간 복잡도	O(V+E)	O(V+E)
추가 공간	역방향 그래프	disc/low/stack
구현 난이도	낮음	중간
실용성	이해하기 쉬움	상수 작음

요약

SCC는 방향 그래프에서 동치 클래스를 정의합니다. 코사라주는 두 번의 DFS로 직관적으로, 타잔은 한 번의 DFS로 low 값을 활용해 구합니다. 압축 그래프(Condensation)를 만들면 복잡한 방향 그래프를 DAG로 단순화해 후속 처리가 쉬워집니다.

---

지난 글: 프림(Prim) 알고리즘 — 그리디 방식으로 MST 확장

다음 글: 단절점과 단절선 — 그래프의 취약 구조 탐지

읽어주셔서 감사합니다. 😊