코사라주 알고리즘 편집하기

'''코사라주 알고리즘'''(Kosaraju's Algorithm)은 방향 그래프에서 강한 연결 요소(SCC, Strongly Connected Components)를 찾는 알고리즘으로, 깊이 우선 탐색(DFS, Depth-First Search)을 두 번 수행하여 SCC를 탐색한다. 이 알고리즘은 O(V + E) 시간 복잡도를 가지며, 타잔 알고리즘과 함께 SCC를 찾는 대표적인 방법이다.
==역사==
코사라주 알고리즘은 1978년 S. Rao Kosaraju가 제안한 알고리즘으로, 방향 그래프에서 SCC를 효과적으로 탐색하는 방법 중 하나로 널리 사용된다. 이 알고리즘은 그래프의 역방향 탐색을 활용하는 것이 특징이다.
==동작 방식 및 예제==
코사라주 알고리즘은 다음과 같은 단계로 동작한다.
*1. 첫 번째 DFS를 수행하여 각 노드의 종료 시간을 기록한다.
*2. 그래프의 모든 간선을 뒤집어(transpose) 새로운 그래프를 만든다.
*3. 종료 시간이 가장 늦은 노드부터 두 번째 DFS를 수행하여 SCC를 찾는다.
'''예제'''

다음 방향 그래프를 예로 들어 동작을 살펴보자.
  0 → 1
   ↖ 2
      ↓  
      3 → 4 → 6 
       ↖ ↓   ↓ ↖ 
          5   7 → 8  
#첫 번째 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 순서로 스택에 저장됨

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

#종료 시간이 가장 늦은 노드부터 두 번째 DFS를 수행하여 SCC를 찾는다.
#*6 → 8 → 7 순서로 탐색됨 → SCC: {6, 7, 8}
#*3 → 5 → 4 순서로 탐색됨 → SCC: {3, 4, 5}
#*0 → 2 → 1 순서로 탐색됨 → SCC: {0, 1, 2}
이제 실제 코드로 확인할 수 있다.
==코드 예제==
<syntaxhighlight lang="python">
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))
</syntaxhighlight>
 출력 결과 예시:
 [[6, 8, 7], [3, 5, 4], [0, 2, 1]]
각 리스트는 하나의 SCC를 나타내며, 해당 그룹 내 모든 노드는 서로 도달 가능하다.
==시간 복잡도==
코사라주 알고리즘의 시간 복잡도는 O(V + E)이며, 두 번의 DFS 탐색을 수행하지만 선형적으로 동작한다.
==응용==
*방향 그래프에서 강한 연결 요소 탐색
*2-SAT 문제 해결
*웹 크롤링 및 네트워크 분석
*전자 회로에서 순환 종속성 탐색
==같이 보기==
*[[타잔 알고리즘]]
*[[강한 연결 요소]]
*[[깊이 우선 탐색]]
==참고 문헌==
*Kosaraju, S. Rao. "Analysis of a graph algorithm." Proceedings of the 1978 Annual Symposium on Foundations of Computer Science, IEEE, 1978.
[[분류:알고리즘]]
[[분류:그래프]]