Kosaraju 알고리즘이란 무엇이며 어떤 문제를 해결할까?

소개

그래프 알고리즘은 처음 보면 복잡해 보이지만, 대부분은 이해하기 쉬운 문제를 해결하기 위해 만들어졌습니다. Kosaraju 알고리즘도 그중 하나입니다.

Kosaraju 알고리즘은 방향 그래프에서 Strongly Connected Components, 즉 강한 연결 요소(SCC) 를 찾는 알고리즘입니다.

이 글에서는 수학적 증명이나 코드부터 시작하지 않고, 먼저 어떤 문제를 해결하려는 알고리즘인지 이해해 보겠습니다.

그래프란 무엇인가?

그래프는 여러 개의 정점(Vertex)과 정점 사이의 간선(Edge)으로 구성됩니다.

예를 들어:

A --- B
|     |
C --- D

그래프는 다음과 같은 시스템을 표현하는 데 사용됩니다.

• 소셜 네트워크
• 도시와 도로
• 서버 간 통신
• 소프트웨어 패키지 의존성
• 웹 페이지 사이의 링크
• 프로그램 실행 흐름
• 마이크로서비스 간 관계

방향 그래프란?

방향 그래프에서는 간선에 방향이 존재합니다.

A → B

이는 A에서 B로 이동할 수 있다는 의미이지만, B에서 A로 돌아갈 수 있다는 뜻은 아닙니다.

소프트웨어에서는:

Service A → Service B

가 Service A가 Service B에 의존한다는 의미일 수 있습니다.

문제는 어디에서 시작될까?

다음 그래프를 보겠습니다.

A → B → C
↑       ↓
└───────┘

D → E

A에서 B로, B에서 C로, 그리고 C에서 다시 A로 이동할 수 있습니다.

따라서:

{A, B, C}

는 서로 매우 강하게 연결된 그룹입니다.

반면:

D → E

에서는 D에서 E로 이동할 수 있지만 E에서 D로 돌아갈 수 없습니다.

Strongly Connected란?

두 정점 u, v가 강하게 연결되어 있다는 것은 다음 두 경로가 모두 존재한다는 의미입니다.

u → ... → v

그리고:

v → ... → u

즉 서로에게 도달할 수 있어야 합니다.

Strongly Connected Component란?

Strongly Connected Component(SCC) 는 그룹 안의 모든 정점이 서로에게 도달할 수 있는 최대 정점 집합입니다.

예를 들어:

A → B → C
↑       ↓
└───────┘

D → E → F
↑       ↓
└───────┘

이 그래프에는:

SCC 1 = {A, B, C}
SCC 2 = {D, E, F}

두 개의 SCC가 있습니다.

Kosaraju 알고리즘은 무엇을 하는가?

Kosaraju 알고리즘의 목적은 방향 그래프 안에 존재하는 모든 SCC를 찾는 것입니다.

예를 들어:

A → B
B → C
C → A
C → D
D → E
E → D

에 대해 결과는:

SCC 1 = {A, B, C}
SCC 2 = {D, E}

가 됩니다.

간단하게 정의하면:

Kosaraju 알고리즘은 방향 그래프를 서로 도달 가능한 정점들의 최대 그룹으로 분해하는 알고리즘입니다.

SCC가 왜 중요한가?

순환 의존성 탐지

Module A → Module B
Module B → Module C
Module C → Module A

이 구조는 Circular Dependency입니다. 세 모듈은 하나의 SCC를 구성합니다.

마이크로서비스

서비스 간 호출 구조에 순환 의존성이 있다면 SCC 분석을 이용해 관련 서비스 그룹을 찾을 수 있습니다.

소셜 네트워크

사용자를 정점으로, Follow 관계를 방향 간선으로 표현하면 서로 도달 가능한 사용자 그룹을 분석할 수 있습니다.

웹 링크 분석

웹 페이지를 정점, 링크를 방향 간선으로 표현하여 강하게 연결된 페이지 집합을 찾을 수 있습니다.

컴파일러와 정적 분석

Control Flow Graph, Call Graph, Dependency Graph와 같은 구조의 순환 영역을 분석하는 데 SCC 개념이 사용됩니다.

패키지 의존성

라이브러리나 패키지 사이의 순환 의존성을 분석하는 데도 활용할 수 있습니다.

일반 DFS만으로는 왜 부족할까?

다음을 생각해 봅시다.

A → B → C

A에서 DFS를 실행하면 A, B, C를 모두 방문할 수 있습니다.

하지만 C에서 B나 A로 돌아갈 수 없으므로 세 정점은 하나의 SCC가 아닙니다.

즉:

Reachability ≠ Strong Connectivity

입니다.

Kosaraju는 이 차이를 구분하기 위해 특별한 순서와 역방향 그래프를 사용합니다.

Kosaraju의 핵심 아이디어

세 단계로 이해할 수 있습니다.

1. 원본 그래프에서 DFS를 수행하고 정점의 종료 순서를 저장합니다.
2. 모든 간선의 방향을 반대로 하여 Transpose Graph를 만듭니다.
3. 첫 번째 DFS에서 얻은 특별한 순서에 따라 Transpose Graph에서 다시 DFS를 수행합니다.

구조는 다음과 같습니다.

Original Graph
      ↓
     DFS
      ↓
Finish Order
      ↓
Transpose Graph
      ↓
     DFS
      ↓
     SCCs

두 번째 단계의 각 DFS 탐색이 하나의 SCC를 찾아냅니다.

간단한 예제

A → B → C
↑       ↓
└───────┘

C → D
D → E
E → D

결과는:

SCC 1 = {A, B, C}
SCC 2 = {D, E}

입니다.

C에서 D로 이동할 수 있지만 D와 E에서는 A, B, C로 돌아갈 수 없으므로 두 그룹은 서로 다른 SCC입니다.

시간 복잡도

Adjacency List를 사용하면 Kosaraju 알고리즘의 시간 복잡도는:

O(V + E)

입니다.

여기서:

• V는 정점의 개수
• E는 간선의 개수

입니다.

따라서 큰 그래프에서도 효율적으로 동작합니다.

다른 SCC 알고리즘도 있을까?

있습니다. 대표적으로:

• Tarjan's Algorithm
• Gabow's Algorithm

이 있습니다.

Tarjan 역시 O(V + E)에 동작하지만, Kosaraju는 구조가 비교적 명확해 SCC를 처음 배울 때 이해하기 좋은 알고리즘입니다.

언제 Kosaraju를 떠올려야 할까?

문제에서 다음과 같은 개념이 등장한다면 SCC를 고려해야 합니다.

• Strong Connectivity
• Mutual Reachability
• Circular Dependency
• 방향 그래프의 컴포넌트
• 순환 서비스 의존성
• 순환 모듈 의존성

Cycle과 SCC의 차이

Cycle은 다음과 같은 닫힌 경로입니다.

A → B → C → A

하지만 SCC는 서로 도달 가능한 정점들의 최대 집합입니다.

하나의 SCC 안에는 여러 개의 서로 다른 Cycle이 존재할 수 있습니다.

정리

Kosaraju 알고리즘은 방향 그래프에서 Strongly Connected Components를 찾는 알고리즘입니다.

SCC는 그룹 안의 모든 정점이 서로에게 도달할 수 있는 최대 정점 집합입니다.

이 개념은 소프트웨어 의존성, 마이크로서비스, 소셜 네트워크, 컴파일러, 웹 그래프, 패키지 관리 등 다양한 분야에서 활용됩니다.

Kosaraju는 두 번의 DFS와 Transpose Graph를 사용하며, Adjacency List 기준 O(V + E) 시간에 동작합니다.

가장 중요한 핵심은 다음과 같습니다.

Kosaraju는 단순히 Cycle 하나를 찾는 알고리즘이 아니라, 방향 그래프를 서로 도달 가능한 최대 그룹으로 분해하는 알고리즘입니다.

다음 글에서는 Kosaraju의 세부 동작에 들어가기 전에 Strongly Connected Components 자체를 더 깊게 살펴보겠습니다.