소개
Kosaraju 알고리즘은 방향 그래프에서 Strongly Connected Components(SCC) 를 찾습니다.
이 글에서는 알고리즘의 이론을 실제 JavaScript와 TypeScript 코드로 옮겨 보겠습니다.
전체 흐름은 다음과 같습니다.
Code
원본 그래프 DFS
↓
Finish Order
↓
모든 간선 반전
↓
Transpose Graph DFS
↓
SCCs그래프 표현
Adjacency List를 Map으로 표현할 수 있습니다.
JavaScript
const graph = new Map([
[0, [1]],
[1, [2, 3]],
[2, [0]],
[3, [4]],
[4, [3]]
]);이 방식은 특히 sparse graph에서 효율적입니다.
첫 번째 DFS
Kosaraju의 첫 DFS에서는 정점을 발견한 순간이 아니라 모든 이웃 처리가 끝난 뒤 Stack에 넣습니다.
JavaScript
function fillOrder(node, graph, visited, stack) {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor, graph, visited, stack);
}
}
stack.push(node);
}이 과정이 Finish Order를 만듭니다.
Transpose Graph 만들기
Code
A → B를:
Code
B → A로 바꿉니다.
JavaScript
function transposeGraph(graph) {
const transpose = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor).push(node);
}
}
return transpose;
}전체 JavaScript 구현
JavaScript
function kosaraju(graph) {
const visited = new Set();
const stack = [];
function fillOrder(node) {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor);
}
}
stack.push(node);
}
for (const node of graph.keys()) {
if (!visited.has(node)) {
fillOrder(node);
}
}
const transpose = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor).push(node);
}
}
visited.clear();
const components = [];
function collect(node, component) {
visited.add(node);
component.push(node);
for (const neighbor of transpose.get(node) ?? []) {
if (!visited.has(neighbor)) {
collect(neighbor, component);
}
}
}
while (stack.length > 0) {
const node = stack.pop();
if (!visited.has(node)) {
const component = [];
collect(node, component);
components.push(component);
}
}
return components;
}TypeScript Generic 구현
TypeScript
type Graph<T> = Map<T, T[]>;Generic을 사용하면 정점이 숫자가 아니라 서비스 이름이어도 사용할 수 있습니다.
TypeScript
function kosaraju<T>(graph: Graph<T>): T[][] {
const visited = new Set<T>();
const stack: T[] = [];
const fillOrder = (node: T): void => {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor);
}
}
stack.push(node);
};
for (const node of graph.keys()) {
if (!visited.has(node)) {
fillOrder(node);
}
}
const transpose: Graph<T> = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor)!.push(node);
}
}
visited.clear();
const components: T[][] = [];
const collect = (node: T, component: T[]): void => {
visited.add(node);
component.push(node);
for (const neighbor of transpose.get(node) ?? []) {
if (!visited.has(neighbor)) {
collect(neighbor, component);
}
}
};
while (stack.length > 0) {
const node = stack.pop()!;
if (!visited.has(node)) {
const component: T[] = [];
collect(node, component);
components.push(component);
}
}
return components;
}Microservice 예제
TypeScript
const services: Graph<string> = new Map([
["user", ["payment"]],
["payment", ["notification"]],
["notification", ["user"]],
["report", ["analytics"]],
["analytics", ["report"]]
]);Kosaraju는 다음과 같은 그룹을 찾을 수 있습니다.
Code
{user, payment, notification}
{report, analytics}이는 실제 시스템에서 순환 의존성을 찾는 데 활용할 수 있습니다.
시간 복잡도
Code
첫 DFS O(V + E)
Transpose O(V + E)
두 번째 DFS O(V + E)따라서 전체 시간 복잡도는:
Code
O(V + E)입니다.
JavaScript 재귀 제한
매우 깊은 그래프에서는 recursive DFS가 다음 오류를 일으킬 수 있습니다.
Code
RangeError: Maximum call stack size exceeded대규모 Production 환경에서는 iterative DFS를 고려하는 것이 좋습니다.
자주 하는 실수
대표적인 실수는 다음과 같습니다.
- Finish 전에 Stack에 정점을 넣는 것
- 두 번째 DFS 전에
visited를 초기화하지 않는 것 - 두 번째 DFS를 원본 그래프에서 실행하는 것
- outgoing edge가 없는 정점을 Map에 등록하지 않는 것
- SCC 내부 순서가 항상 동일하다고 가정하는 것
정리
Kosaraju 구현의 핵심 흐름은 다음과 같습니다.
Code
DFS
↓
Finish Order
↓
Transpose
↓
DFS
↓
SCCsAdjacency List를 사용하면 시간 복잡도는 O(V + E)입니다.
TypeScript의 Generic과 Type Safety를 이용하면 Module, Package, Microservice 의존성 분석과 같은 실제 시스템에서도 재사용하기 좋은 구조를 만들 수 있습니다.
가장 중요한 개념은 다음과 같습니다.
첫 번째 DFS는 올바른 처리 순서를 만들고, Transpose는 도달 방향을 뒤집으며, 두 번째 DFS는 SCC의 경계를 분리합니다.