---
title: "위상 정렬: 진입 차수 0의 의미와 cycle을 검출하는 Java Kahn 알고리즘"
slug: "java-topological-sort"
category: "CS"
topic: "cs"
subtopic: "algorithms"
tags: ["Java","Topological Sort","DAG","Kahn Algorithm","Dependency"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "DAG 의존 관계에서 indegree와 ready queue의 불변식을 추적하고, 결과 길이로 cycle을 검출하며 결정성·메모리·배포 운영 기준까지 연결한다."
kind: "Deep Dive"
evidence: "Princeton Algorithms 4/e directed graph 자료·Kahn 1962 원 논문·Java SE 21 Queue API를 대조하고 TopologicalSortDemo를 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

위상 정렬은 directed edge `u -> v`를 “u가 v보다 먼저 와야 한다”로 해석해 모든 제약을 만족하는 순서를 만든다. 가능한 입력은 DAG다. cycle이 있으면 어느 정점도 cycle 안의 predecessor보다 먼저 올 수 없어 순서 자체가 존재하지 않는다.

## 1. 문제 계약과 결과의 비유일성

입력은 정점 `0..V-1`의 directed adjacency다. 모든 edge `u->v`에 대해 결과에서 u의 위치가 v보다 앞서야 한다. graph가 비면 빈 순서, cycle이면 부분 결과를 반환하지 않고 예외를 던진다.

위상 순서는 일반적으로 여러 개다. 예제는 indegree 0 정점을 index 순으로 초기 queue에 넣고 FIFO로 처리해 결정적인 한 결과를 만든다. lexicographically smallest 결과가 필요하면 ready set을 PriorityQueue로 바꾸며 비용은 $O((V+E)\log V)$ 쪽으로 달라진다.

## 2. indegree는 “남은 선행 조건 수”다

graph `0->2, 1->2, 1->3, 2->4, 3->4`를 추적한다.

| 단계 | ready queue | 제거 정점 | 감소한 indegree | 새 ready |
| ---: | --- | ---: | --- | --- |
| 초기 | `[0,1]` | - | `[0,0,2,1,2]` | 0,1 |
| 1 | `[0,1]` | 0 | `in[2]:2→1` | 없음 |
| 2 | `[1]` | 1 | `in[2]:1→0`, `in[3]:1→0` | 2,3 |
| 3 | `[2,3]` | 2 | `in[4]:2→1` | 없음 |
| 4 | `[3]` | 3 | `in[4]:1→0` | 4 |

**불변식:** 아직 출력하지 않은 각 정점의 indegree는 아직 제거하지 않은 predecessor edge 수다. ready queue에는 그 수가 0이 된 정점만 있다. 그러므로 queue에서 꺼낸 정점은 지금 출력해도 어떤 미처리 선행 조건도 위반하지 않는다.

## 3. 정당성과 cycle 검출

DAG에는 indegree 0 정점이 적어도 하나 있다. 없다면 임의 정점에서 predecessor를 계속 따라가 유한 정점 중 하나를 다시 만나 cycle이 된다. indegree 0 정점을 제거한 나머지도 DAG이므로 귀납적으로 모든 정점을 출력할 수 있다.

반대로 algorithm이 V개보다 적게 출력하고 queue가 비면 남은 모든 정점의 indegree가 양수다. 남은 subgraph에 cycle이 있어야 하므로 `written != V`가 cycle 증거다. 단순히 “queue가 비었다”만 보면 정상적인 마지막 상태와 구분되지 않는다.

## 실행 재현

아래 코드는 설명용 조각이 아니라 `main`에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

```java
import java.util.Arrays;

public final class TopologicalSortDemo {
    static int[] sort(int[][] graph) {
        if (graph == null) throw new IllegalArgumentException("graph must not be null");
        int[] indegree = new int[graph.length];
        for (int[] edges : graph) {
            if (edges == null) throw new IllegalArgumentException("adjacency must not be null");
            for (int next : edges) {
                if (next < 0 || next >= graph.length) throw new IllegalArgumentException("invalid edge");
                indegree[next]++;
            }
        }
        int[] queue = new int[graph.length];
        int head = 0, tail = 0;
        for (int v = 0; v < graph.length; v++) if (indegree[v] == 0) queue[tail++] = v;
        int[] order = new int[graph.length];
        int written = 0;
        while (head < tail) {
            int current = queue[head++];
            order[written++] = current;
            for (int next : graph[current]) if (--indegree[next] == 0) queue[tail++] = next;
        }
        if (written != graph.length) throw new IllegalArgumentException("cycle detected");
        return order;
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    static void expectCycle(int[][] graph) {
        try { sort(graph); throw new AssertionError("cycle expected"); }
        catch (IllegalArgumentException expected) {
            check(expected.getMessage().equals("cycle detected"), "cycle reason");
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{2}, {2, 3}, {4}, {4}, {}};
        int[] order = sort(graph);
        check(Arrays.equals(order, new int[] {0, 1, 2, 3, 4}), "deterministic order");
        check(sort(new int[0][]).length == 0, "empty");
        expectCycle(new int[][] {{1}, {2}, {0}});
        System.out.println("order=" + Arrays.toString(order) + ", cycle=rejected");
    }
}
```

```bash
javac --release 21 TopologicalSortDemo.java
java TopologicalSortDemo
```

직접 실행한 출력은 다음과 같다.

```text
order=[0, 1, 2, 3, 4], cycle=rejected
```

컴파일러와 런타임은 `javac 21.0.11`, OpenJDK `21.0.11`을 사용했다. `assert` 옵션에 의존하지 않고 실패 시 `AssertionError`를 던지므로 위 명령 그대로 검증된다.


## 4. 복잡도와 메모리

indegree 계산에서 모든 adjacency entry를 한 번 보고, 제거 단계에서 각 edge를 한 번 더 감소시킨다. 정점도 queue에 최대 한 번 들어가므로 시간은 $O(V+E)$이다. indegree, queue, result가 각각 길이 V라 보조 공간은 $O(V)$. 입력 adjacency $O(V+E)$는 별도다.

예제는 primitive `int[]`를 사용해 boxing과 queue object를 피한다. dynamic graph나 generic node라면 `ArrayDeque<Integer>`가 구현 편의성을 준다. indegree를 복사하지 않고 직접 변경하면 caller graph metadata를 오염할 수 있으므로 ownership 계약을 명시한다.

## 5. JVM과 large DAG

세 primitive array와 adjacency arrays는 heap에 있다. head/tail/written/current는 frame local variable 관점이다. recursion을 쓰지 않아 깊은 chain이 JVM Stack을 소비하지 않는다. 그래도 V와 E가 크면 adjacency와 result를 동시에 유지하는 peak heap이 문제다.

실제 build graph에서는 node ID를 String으로 두고 `Map<String,Integer>`로 압축하는 과정의 node/boxing allocation이 더 클 수 있다. JFR allocation, heap histogram, max ready queue를 관측한다.

## 6. DFS 기반 위상 정렬과 비교

DFS postorder도 DAG 위상 순서를 만들 수 있고 gray state로 back-edge cycle을 찾는다. Kahn은 ready task 집합과 indegree가 노출되어 scheduler와 병렬 실행에 자연스럽다. DFS는 cycle 경로를 복원하기 쉬운 편이지만 깊은 graph의 recursion risk가 있다. 둘은 정답이 같아야 하는 경쟁 구현이 아니라 필요한 운영 상태가 다르다.

## 7. 실제 도메인 적용

CI build target, database migration dependency, 배포 component, course prerequisite에 쓴다. scheduler에서는 ready queue 크기, critical path, resource wait, failed node와 blocked downstream 수를 본다. 위상 순서만으로 병렬 실행 안전성이 보장되지는 않는다. 두 ready task가 같은 DB table을 변경하면 별도 resource lock 계약이 필요하다.

동적 edge가 자주 추가되는 시스템에서 매번 전체 정렬하면 비싸다. incremental topological ordering은 별도 알고리즘이며 consistency와 cycle rejection의 atomicity를 설계해야 한다.

## 8. 이건 피한다

- **cycle에서 부분 순서를 정상 결과로 반환한다.** downstream 일부만 실행되어 시스템 상태가 어긋난다. 결과 수를 V와 비교해 전체를 거절한다.
- **위상 순서가 유일하다고 가정한다.** ready가 여러 개면 결과가 달라진다. 결정성 요구가 있으면 priority 규칙을 명시한다.
- **undirected graph에 적용한다.** 양방향 edge는 두 정점 cycle처럼 보인다. dependency 방향을 모델링한다.
- **준비된 task면 동시에 실행해도 된다고 본다.** graph 밖 shared resource conflict가 남는다. lock/resource constraint를 별도 검사한다.
- **indegree mutation ownership을 숨긴다.** 공유 배열을 훼손할 수 있다. method 내부 copy나 일회성 소유권을 명시한다.

## Reference

- Arthur B. Kahn, [Topological sorting of large networks, Communications of the ACM 5(11), 1962](https://doi.org/10.1145/368996.369025)
- Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Directed Graphs](https://algs4.cs.princeton.edu/42digraph/)
- Robert Sedgewick, Kevin Wayne, [Topological.java](https://algs4.cs.princeton.edu/42digraph/Topological.java.html)
- Oracle, [Queue — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Queue.html)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — Heap and Frames](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)