코사라주 알고리즘

코사라주 알고리즘(Kosaraju's Algorithm)은 방향 그래프에서 강한 연결 요소(SCC, Strongly Connected Components)를 찾는 알고리즘으로, 깊이 우선 탐색(DFS, Depth-First Search)을 두 번 수행하여 SCC를 탐색한다. 이 알고리즘은 O(V + E) 시간 복잡도를 가지며, 타잔 알고리즘과 함께 SCC를 찾는 대표적인 방법이다.

1 역사

코사라주 알고리즘은 1978년 S. Rao Kosaraju가 제안한 알고리즘으로, 방향 그래프에서 SCC를 효과적으로 탐색하는 방법 중 하나로 널리 사용된다. 이 알고리즘은 그래프의 역방향 탐색을 활용하는 것이 특징이다.

2 동작 방식 및 예제

코사라주 알고리즘은 다음과 같은 단계로 동작한다.

• 1. 첫 번째 DFS를 수행하여 각 노드의 종료 시간을 기록한다.
• 2. 그래프의 모든 간선을 뒤집어(transpose) 새로운 그래프를 만든다.
• 3. 종료 시간이 가장 늦은 노드부터 두 번째 DFS를 수행하여 SCC를 찾는다.

예제

다음 방향 그래프를 예로 들어 동작을 살펴보자.

 0 → 1
  ↖ 2
     ↓  
     3 → 4 → 6 
      ↖ ↓   ↓ ↖ 
         5   7 → 8  

1. 첫 번째 DFS를 수행하여 각 노드의 종료 시간을 기록한다.
   • 0번 노드 방문 → 1 → 2 → 0 순서로 탐색됨
   • 2 → 3 이동 → 3 → 4 → 5 → 3 탐색됨
   • 3에서 DFS 종료 → 5 → 4 → 3 순서로 스택에 저장됨
   • 6번 노드 방문 → 7 → 8 → 6 탐색됨
   • 6에서 DFS 종료 → 8 → 7 → 6 순서로 스택에 저장됨

1. 그래프의 모든 간선을 뒤집는다.
   • 방향을 반대로 설정하여 새 그래프를 생성

1. 종료 시간이 가장 늦은 노드부터 두 번째 DFS를 수행하여 SCC를 찾는다.
   • 6 → 8 → 7 순서로 탐색됨 → SCC: {6, 7, 8}
   • 3 → 5 → 4 순서로 탐색됨 → SCC: {3, 4, 5}
   • 0 → 2 → 1 순서로 탐색됨 → SCC: {0, 1, 2}

이제 실제 코드로 확인할 수 있다.

3 코드 예제

from collections import defaultdict

def kosaraju_scc(graph):
    def dfs1(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs1(neighbor)
        stack.append(node)

    def dfs2(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in reversed_graph[node]:
            if neighbor not in visited:
                dfs2(neighbor, component)

    # 1. 첫 번째 DFS 수행하여 스택 채우기
    visited = set()
    stack = []
    for node in graph:
        if node not in visited:
            dfs1(node)

    # 2. 그래프의 모든 간선을 뒤집기
    reversed_graph = defaultdict(list)
    for node in graph:
        for neighbor in graph[node]:
            reversed_graph[neighbor].append(node)

    # 3. 스택에서 꺼낸 순서대로 두 번째 DFS 수행
    visited.clear()
    sccs = []
    while stack:
        node = stack.pop()
        if node not in visited:
            component = []
            dfs2(node, component)
            sccs.append(component)

    return sccs

# 예제 그래프 (방향 그래프)
graph = {
    0: [1],
    1: [2],
    2: [0, 3],
    3: [4],
    4: [5, 6],
    5: [3],
    6: [7],
    7: [8],
    8: [6]
}

# 강한 연결 요소 출력
print(kosaraju_scc(graph))

출력 결과 예시:
[[6, 8, 7], [3, 5, 4], [0, 2, 1]]

각 리스트는 하나의 SCC를 나타내며, 해당 그룹 내 모든 노드는 서로 도달 가능하다.

4 시간 복잡도

코사라주 알고리즘의 시간 복잡도는 O(V + E)이며, 두 번의 DFS 탐색을 수행하지만 선형적으로 동작한다.

5 응용

• 방향 그래프에서 강한 연결 요소 탐색
• 2-SAT 문제 해결
• 웹 크롤링 및 네트워크 분석
• 전자 회로에서 순환 종속성 탐색

6 같이 보기

• 타잔 알고리즘
• 강한 연결 요소
• 깊이 우선 탐색

7 참고 문헌

• Kosaraju, S. Rao. "Analysis of a graph algorithm." Proceedings of the 1978 Annual Symposium on Foundations of Computer Science, IEEE, 1978.