강한 결합 요소

강한 결합 요소(Strongly Connected Component, SCC)는 방향 그래프에서 모든 정점이 서로 도달 가능한 최대 부분 그래프를 의미한다. 즉, 강한 결합 요소 내부에서는 임의의 두 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재해야 한다.

• 즉 쉽게 말해, 직접 가든 다른 곳을 거치든 서로 갈 수 있는 정점의 집합이라고 보면 된다.
  • 만약, A, B, C, D가 서로 갈 수 있는 길이 있는데, E는 A, B, C, D로 모두 갈 수 있는 반면, E에서 D로 가는 길만 없다면, E는 강한 결합 요소가 아니게 된다.
• 사이클이 있다면 그 사이클의 구성요소는 무조건 강한 결합 요소이다.

1 개요

방향 그래프(Directed Graph)에서 강한 결합 요소는 다음과 같은 성질을 만족하는 최대 부분 그래프이다.

• SCC 내부의 모든 정점 쌍 (u, v)에 대해 u → v, v → u인 경로가 존재한다.
• SCC를 정점으로 축소하면 DAG(방향 비순환 그래프, Directed Acyclic Graph)를 형성한다.

예를 들어, 다음 방향 그래프를 고려하자.

1 → 2 → 3
↑   ↓   ↓
4 ← 5 → 6 ↔ 7

이 그래프의 강한 결합 요소는 다음과 같다.

• {1, 2, 4, 5} - 서로 왕복 가능한 경로가 존재
• {6, 7} - 서로 직접 왕복 가능
• 나머지는 모두 강한 결합 요소가 아니다. 만약 7이 3으로 가는 경로가 존재했다면 {3, 6, 7}이은 강한 결합요소였을 것이다.

2 강한 결합 요소 찾기 알고리즘

강한 결합 요소를 찾는 대표적인 알고리즘으로는 코사라주 알고리즘(Kosaraju's Algorithm)과 타잔 알고리즘(Tarjan's Algorithm)이 있다. 각 구현 코드는 각 문서를 참고하자.

2.1 코사라주 알고리즘(Kosaraju's Algorithm)

코사라주 알고리즘은 DFS(깊이 우선 탐색)을 두 번 수행하여 SCC를 찾는다.

1. 방향 그래프에서 DFS를 수행하여 탐색 완료 순서(탐색 종료 시간이 큰 순서)를 기록한다.
2. 그래프의 방향을 반전(reverse)하여 모든 간선을 뒤집는다.
3. 반전된 그래프에서 DFS를 수행하되, 탐색 종료 순서의 역순으로 시작하여 SCC를 찾는다.

2.2 타잔 알고리즘(Tarjan's Algorithm)

타잔 알고리즘은 **한 번의 DFS 탐색으로 SCC를 찾는 알고리즘**으로, 각 정점의 DFS 방문 순서(low-link 값)를 활용한다.

1. DFS를 수행하며 각 노드의 방문 순서를 기록한다.
2. DFS 탐색 중 가장 작은 도달 가능한 노드(low-link 값)를 갱신한다.
3. DFS가 백트래킹할 때, 현재 노드의 low-link 값이 자신의 방문 순서와 같다면 SCC의 루트임을 확인하고 해당 SCC를 추출한다.

3 강한 결합 요소와 DAG

SCC를 하나의 노드로 축소하면 방향 비순환 그래프(DAG)가 형성된다. 이는 그래프에서 사이클을 제거하고 위상 정렬을 수행할 때 유용하다.

예를 들어, 아래 방향 그래프에서 SCC를 찾고 축소하면:

1 → 2 → 3
↑   ↓   ↓ ↖
4 ← 5 → 6 ↔ 7

강한 결합 요소:

• {1, 2, 4, 5}
• {3, 6, 7}

SCC를 하나의 노드로 압축하면 DAG가 된다.

{1, 2, 4, 5} → {3, 6, 7} 

4 구현 소스코드

아래는 SCC를 구하고 DAG까지 산출해주는 소스코드이다. 코르사주를 기반으로 하고 있지만 코르사주 알고리즘을 철저히 따르진 않고 좀 더 계량된 버전이다. 순수한 코르사주 알고리즘을 보고 싶다면 해당 문서를 참고하면 된다.

from collections import defaultdict

# Step 1: Reverse Graph Function
def reverse_graph(graph):
    """Reverse the directed graph"""
    rev_graph = defaultdict(list)
    for u in graph:
        for v in graph[u]:
            rev_graph[v].append(u)
    return rev_graph

# Step 2: DFS for Reckless Ranking
def dfs_rank(graph, node, visited, stack):
    """DFS to determine finishing times (Reckless Ranking)"""
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_rank(graph, neighbor, visited, stack)
    stack.append(node)  # Store nodes in finishing order

# Step 3: DFS for SCC Computation
def dfs_scc(graph, node, visited, component):
    """DFS to extract strongly connected components"""
    visited.add(node)
    component.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_scc(graph, neighbor, visited, component)

# SCC Driver using iRank order
def scc_driver(graph, iRank):
    """Compute SCCs by running DFS on G in iRank order"""
    visited = set()
    sccs = []

    while iRank:
        node = iRank.pop()  # Process nodes in decreasing finishing order
        if node not in visited:
            component = []
            dfs_scc(graph, node, visited, component)
            sccs.append(component)

    return sccs

# Kosaraju-Sharir SCC Algorithm
def find_sccs(graph):
    """Compute SCCs using Kosaraju-Sharir Algorithm with iRank"""
    rev_graph = reverse_graph(graph)
    
    # Step 2: Reckless Ranking (DFS on G_rev to get finishing times)
    visited = set()
    stack = []
    for node in graph:
        if node not in visited:
            dfs_rank(rev_graph, node, visited, stack)

    # Step 3: SCC Computation using SCC Driver (DFS on G in iRank order)
    sccs = scc_driver(graph, stack)
    return sccs

# Step 4: Compute Reduced Graph G^c
def build_reduced_graph(graph, sccs):
    """Build the reduced graph G^c where each SCC is treated as a single node"""
    scc_map = {node: i for i, scc in enumerate(sccs) for node in scc}
    reduced_graph = defaultdict(set)

    for u in graph:
        for v in graph[u]:
            if scc_map[u] != scc_map[v]:  # Only keep inter-SCC edges
                reduced_graph[scc_map[u]].add(scc_map[v])
    
    return reduced_graph, scc_map

# Corrected Graph Definition (G9)
graph_G9 = {
    "a": ["d"],
    "b": ["a", "c"],
    "c": ["b"],
    "d": ["g", "h"],
    "e": ["a", "b", "h", "i"],
    "f": ["c", "e"],
    "g": ["h"],
    "h": ["a"],
    "i": ["f", "h"]
}

# Execute SCC Algorithm with iRank
sccs = find_sccs(graph_G9)
reduced_graph, scc_map = build_reduced_graph(graph_G9, sccs)

# Print SCC Results
print("\n📌 Strongly Connected Components (SCCs):")
for i, scc in enumerate(sccs, 1):
    print(f"  SCC {i}: {scc}")

# Print Reduced Graph
print("\n📌 Corrected Reduced Graph (G^c):")
for scc_id, neighbors in reduced_graph.items():
    print(f"  SCC {sccs[scc_id]} → { [sccs[n] for n in neighbors] }")

실행 결과

📌 Strongly Connected Components (SCCs):
  SCC 1: ['a', 'd', 'g', 'h']
  SCC 2: ['b', 'c']
  SCC 3: ['f', 'e', 'i']

📌 Corrected Reduced Graph (G^c):
  SCC ['b', 'c'] → [['a', 'd', 'g', 'h']]
  SCC ['f', 'e', 'i'] → [['a', 'd', 'g', 'h'], ['b', 'c']]

5 강한 결합 요소의 활용

1. 그래프 압축 - 강한 결합 요소를 노드로 변환하여 DAG로 단순화 가능.
2. 위상 정렬 - SCC를 DAG로 변환 후 정렬하여 순서를 분석.
3. 2-SAT 문제 해결 - 논리식에서 강한 결합 요소를 이용해 만족 가능성을 판별.
4. 인터넷 네트워크 분석 - 통신망에서 강한 결합된 컴포넌트를 찾는 데 활용.

6 같이 보기

• 깊이 우선 탐색
• 위상 정렬
• DAG (방향 비순환 그래프)
• 코사라주 알고리즘
• 타잔 알고리즘