코사라주를 사용한 강한 연결 요소

강한 연결 요소의 정의

코사라주 알고리즘: 두 번의 DFS 탐색

코사라주 알고리즘이 동작하는 이유

1단계: 종료 순서 구성

from collections import defaultdict

def kosaraju(n, edges):
    graph = defaultdict(list)
    rev_graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        rev_graph[v].append(u)  # reversed edges
    
    visited = set()
    finish_stack = []
    
    def dfs1(node):
        visited.add(node)
        for nxt in graph[node]:
            if nxt not in visited:
                dfs1(nxt)
        finish_stack.append(node)  # push after all neighbours done
    
    for i in range(n):
        if i not in visited:
            dfs1(i)
    
    return finish_stack, rev_graph

2단계: 전치 그래프에서 DFS

from collections import defaultdict

def kosaraju_full(n, edges):
    graph = defaultdict(list)
    rev_graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        rev_graph[v].append(u)
    
    visited = set()
    finish_stack = []
    
    def dfs1(node):
        visited.add(node)
        for nxt in graph[node]:
            if nxt not in visited: dfs1(nxt)
        finish_stack.append(node)
    
    for i in range(n):
        if i not in visited: dfs1(i)
    
    visited.clear()
    sccs = []
    
    def dfs2(node, component):
        visited.add(node)
        component.append(node)
        for nxt in rev_graph[node]:
            if nxt not in visited: dfs2(nxt, component)
    
    while finish_stack:
        node = finish_stack.pop()
        if node not in visited:
            component = []
            dfs2(node, component)
            sccs.append(component)
    
    return sccs

# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges))  # [[3], [0,2,1]] or similar

그래프 전치

대규모 그래프를 위한 반복형 버전

def dfs1_iterative(start, graph, visited, finish_stack):
    stack = [(start, iter(graph[start]))]
    visited.add(start)
    while stack:
        node, neighbours = stack[-1]
        try:
            nxt = next(neighbours)
            if nxt not in visited:
                visited.add(nxt)
                stack.append((nxt, iter(graph[nxt])))
        except StopIteration:
            stack.pop()
            finish_stack.append(node)

print('Iterative DFS for large graphs avoids recursion limit')

Tarjan 알고리즘: SCC의 대안

SCC의 활용

응축 DAG

def build_condensation(n, edges, sccs):
    # Assign each node to its SCC index
    scc_id = [0] * n
    for idx, component in enumerate(sccs):
        for node in component:
            scc_id[node] = idx
    
    # Build condensation edges
    condensation_edges = set()
    for u, v in edges:
        su, sv = scc_id[u], scc_id[v]
        if su != sv:
            condensation_edges.add((su, sv))
    
    return list(condensation_edges)

edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs))  # [(0,1)] or [(1,0)]

SCC의 수와 그래프 속성

빠른 확인

단원 복습