고급 그래프 분석에서 SCC와 절단점을 찾는 방법

순환 의존과 단일 장애점을 그래프에서 분리하기

모듈 의존성의 순환, 네트워크의 취약 노드, 서비스 간 결합 관계는 그래프 구조를 분해해야 명확해진다. 방향 그래프에서는 강결합요소(SCC)를 찾아 서로 되돌아갈 수 있는 정점 묶음을 분리하고, 무방향 그래프에서는 절단점을 찾아 제거 시 연결이 끊기는 지점을 확인한다.

SCC는 방향 그래프에서 모든 정점 쌍이 서로 도달 가능한 최대 부분 그래프 집합이다. 절단점은 무방향 그래프에서 해당 정점을 제거했을 때 연결 요소 개수가 늘어나는 정점이다.

Tarjan 알고리즘은 하나의 DFS 패스에서 각 정점의 방문 순서(index)와 역방향 최소 도달값(low-link)을 계산한다. 활성 경로의 정점을 스택으로 관리하다가 SCC의 루트를 만나면 스택에서 정점을 꺼내 하나의 컴포넌트를 만든다. 시간 복잡도는 O(V+E), 추가 메모리는 O(V)이며 재귀 DFS와 반복 DFS 모두로 구현할 수 있다.

Kosaraju 알고리즘은 DFS를 두 번 수행한다. 첫 DFS에서 종료 시각 순서를 기록하고, 그 역순으로 전치 그래프(transpose)를 탐색해 SCC를 추출한다. 시간 복잡도는 전치 그래프 구성 비용을 포함해 O(V+E)이며, 단계를 나눌 수 있어 분산 처리에 적용하기 쉽다.

절단점 탐지는 DFS 트리의 disc와 low를 사용한다. 루트 정점은 자식 수가 2 이상이면 절단점이고, 루트가 아닌 정점 u는 자식 v 중 low[v] >= disc[u]인 경우 절단점이다. 이 역시 O(V+E)에 수행되며 네트워크 취약 노드 식별에 활용된다.

DFS의 방문 시각과 low-link가 판단 근거가 된다

disc 또는 idx는 정점을 처음 방문한 시각을 기록한다. low는 역방향 간선이나 서브트리 경로를 통해 닿을 수 있는 가장 이른 disc 값을 유지한다. 이 두 값의 관계가 SCC의 경계와 절단점 여부를 가르는 기준이다.

Tarjan에서는 활성 경로의 정점을 스택에 넣고, low == idx가 되는 루트에서 스택을 팝해 SCC를 구성한다. Kosaraju는 첫 DFS의 종료 순서를 보관한 뒤 전치 그래프에서 두 번째 DFS를 진행한다.

그래프 표현은 인접 리스트를 쓰는 편이 O(V+E) 접근에 적합하다. Kosaraju는 전치 그래프가 필요하지만 Tarjan과 절단점 탐지는 원 그래프만으로 처리할 수 있다.

대규모 그래프는 재귀 한계를 넘을 수 있다. 반복 DFS, 꼬리재귀 제거, 언어별 스택 제한을 검토해야 한다. 분리 그래프에서는 모든 미방문 정점에서 DFS를 시작해야 하며, 자기 루프와 중복 간선의 처리 기준도 입력 단계에서 정해야 한다.

Tarjan은 단일 패스와 캐시 지역성 면에서 유리하지만 병렬화는 어렵다. Kosaraju는 단계를 분리할 수 있어 파티셔닝과 분산 실행에 상대적으로 적합하다. 절단점 탐지는 본질적으로 순차 DFS에 가깝고, 그래프 파티션을 나눈 뒤 병합할 때는 교점 처리 로직이 추가로 필요하다.

알고리즘 선택과 예외 처리를 한 흐름으로 보기

⤢✕

항목	Tarjan’s SCC	Kosaraju’s SCC	Articulation Points
성능(시간)	O(V+E) 단일 패스	O(V+E) + 전치 구성	O(V+E)
확장성	병렬화 어려움, 캐시 우수	단계 분리로 분산/병렬 용이	파티션 병합 로직 필요
일관성	결정적 결과, 스택 순서에 따라 SCC 출력 순서만 변동	결정적 결과, 종료순서 기반	결정적 결과
안정성	재귀 깊이 이슈 가능, 반복 DFS로 완화	전치 그래프 메모리 추가	재귀 깊이 이슈 가능
운영 편의	구현 중간 난이도, 스택 관리 주의	구현 용이, 그래프 2배 저장 고려	구현 용이, 루트/임계조건 주의

Python 구현에서 확인할 전제

환경과 전제는 Python 3.10+ 및 인접 리스트 형태(List[List[int]])다. 정점은 0..n-1을 가정하며, 입력이 큰 경우 재귀 한계를 조정하거나 반복 DFS를 고려한다.

Tarjan’s SCC

from typing import List

def tarjan_scc(n: int, adj: List[List[int]]) -> List[List[int]]:
    import sys
    sys.setrecursionlimit(max(1_000_000, n * 2))
    index = 0
    idx = [-1] * n
    low = [0] * n
    onstack = [False] * n
    stack = []
    comps: List[List[int]] = []

    def dfs(v: int):
        nonlocal index
        idx[v] = index
        low[v] = index
        index += 1
        stack.append(v)
        onstack[v] = True
        for w in adj[v]:
            if idx[w] == -1:
                dfs(w)
                low[v] = min(low[v], low[w])
            elif onstack[w]:
                low[v] = min(low[v], idx[w])
        if low[v] == idx[v]:
            comp = []
            while True:
                w = stack.pop()
                onstack[w] = False
                comp.append(w)
                if w == v:
                    break
            comps.append(comp)

    for v in range(n):
        if idx[v] == -1:
            dfs(v)
    return comps

# 사용 예시
if __name__ == "__main__":
    # 0->1->2->0, 1->3, 3->4->5->3
    n = 6
    adj = [
        [1],    # 0
        [2, 3], # 1
        [0],    # 2
        [4],    # 3
        [5],    # 4
        [3],    # 5
    ]
    print("Tarjan SCC:", tarjan_scc(n, adj))

Kosaraju’s SCC

from typing import List

def kosaraju_scc(n: int, adj: List[List[int]]) -> List[List[int]]:
    visited = [False] * n
    order: List[int] = []

    def dfs1(v: int):
        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)

    # 전치 그래프
    radj = [[] for _ in range(n)]
    for v in range(n):
        for w in adj[v]:
            radj[w].append(v)

    visited = [False] * n
    comps: List[List[int]] = []

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

    for v in reversed(order):
        if not visited[v]:
            comp: List[int] = []
            dfs2(v, comp)
            comps.append(comp)

    return comps

# 사용 예시
if __name__ == "__main__":
    n = 6
    adj = [
        [1],
        [2, 3],
        [0],
        [4],
        [5],
        [3],
    ]
    print("Kosaraju SCC:", kosaraju_scc(n, adj))

Articulation Points (절단점)

from typing import List, Set

def articulation_points(n: int, adj: List[List[int]]) -> Set[int]:
    """
    adj: 무방향 그래프 인접 리스트. 양방향 간선 모두 포함되어야 함.
    """
    import sys
    sys.setrecursionlimit(max(1_000_000, n * 2))
    disc = [-1] * n
    low = [0] * n
    parent = [-1] * n
    ap: Set[int] = set()
    time = 0

    def dfs(u: int):
        nonlocal time
        children = 0
        disc[u] = low[u] = time
        time += 1
        for v in adj[u]:
            if disc[v] == -1:
                parent[v] = u
                children += 1
                dfs(v)
                low[u] = min(low[u], low[v])
                if parent[u] == -1 and children > 1:
                    ap.add(u)
                if parent[u] != -1 and low[v] >= disc[u]:
                    ap.add(u)
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

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

    return ap

# 사용 예시
if __name__ == "__main__":
    # 무방향: 0-1-2, 1-3-4, 절단점은 1, 3
    n = 5
    adj_undirected = [
        [1],        # 0
        [0, 2, 3],  # 1
        [1],        # 2
        [1, 4],     # 3
        [3],        # 4
    ]
    print("Articulation Points:", articulation_points(n, adj_undirected))

Tarjan과 Kosaraju는 [[2,1,0], [5,4,3]]처럼 두 개의 SCC를 반환하며, 출력 순서는 구현 세부에 따라 달라질 수 있다. 절단점 구현은 {1, 3}을 반환한다.

분리 그래프는 각 정점의 방문 여부를 확인하며 DFS를 시작해야 한다. 자기 루프와 다중 간선은 알고리즘의 정합성에 미치는 영향이 작지만, 성능을 위해 중복 간선 제거를 고려할 수 있다. 긴 사슬형 데이터에서는 반복 DFS나 재귀 한계 조정이 필요하다.

의존성 분석과 네트워크 설계에 적용하기

모듈 또는 마이크로서비스 의존성 그래프에서는 SCC를 이용해 순환 의존을 자동으로 찾고, 배포 순서와 격리 전략을 세울 수 있다. 빌드 시스템과 컴파일러에서도 사이클을 검출·분해해 위상 정렬이 가능한 영역을 분리한다.

절단점은 네트워크의 중요 노드를 식별하는 기준이 된다. 고가용성 설계에서는 이 지점을 중심으로 이중화 우선순위를 정하고, 단일 장애점 제거 및 우회 구조 설계로 장애 전파를 줄일 수 있다.

소셜·추천 그래프에서는 강결합 커뮤니티를 추출해 확산 경로와 폐회로를 파악하고 AB 테스트 타깃팅에 사용할 수 있다. 지식 그래프와 웹 크롤링에서는 SCC를 기준으로 강결합 영역의 페이지를 묶어 처리하며 크롤링 큐를 최적화한다.

사이클과 절단점 탐지는 O(V+E)로 수행할 수 있어 탐지 비용을 크게 낮춘다. SCC를 배포·롤백 단위로 삼으면 변경 영향 범위를 줄일 수 있으며, 대규모 의존성 그래프의 분석 시간은 수 시간에서 분 단위로 단축될 수 있다.

운영 제약에 맞춰 구현을 선택하는 기준

인접 리스트를 사용하고 ID를 연속적으로 매핑하면 캐시 적중률을 확보할 수 있다. Kosaraju를 채택한다면 전치 그래프를 미리 유지할지, 필요할 때 생성할지 메모리와 CPU의 균형을 고려해야 한다.

대규모 그래프는 반복 DFS, 스택 풀링, 메모리 재사용을 검토할 대상이다. 분산 또는 스트리밍 환경에서는 Kosaraju의 1차·2차 단계를 배치로 나누고, 파티션 간 컷 경계를 처리하는 방식을 설계한다.

정확성 검증은 작은 그래프의 참값을 직접 비교한 뒤 무작위 그래프 퍼지 테스트로 넓힐 수 있다. 방문 순서와 low 값을 기록하는 옵션, 재현 가능한 시드 기반 그래프 생성도 문제 분석과 운영 관측에 도움이 된다.

Tarjan은 단일 패스와 캐시 지역성을 우선할 때, Kosaraju는 단계 분리와 분산 적용 가능성을 우선할 때 선택할 수 있다. 절단점 탐지는 네트워크와 시스템 구조의 단일 장애점을 확인하는 핵심 수단이며, 대규모 환경에서는 반복 DFS, 그래프 파티션, 관측 가능성을 함께 설계해야 한다.