선행 작업과 위상 정렬 순서
위상 정렬은 작업을 실행하는 스케줄러가 아니라, 방향 간선이 표현한 선행 조건을 만족하는 정점 배열을 계산하는 단계입니다. 따라서 각 작업의 실제 성공·실패 상태와 별도로 그래프의 구조적 유효성을 판정해야 합니다.
앱 배포 D는 빌드 B와 데이터 준비 C가 끝난 뒤 실행하고, B와 C는 설정 A가 준비된 뒤 시작한다고 합시다. 의존 관계를 A→B, A→C, B→D, C→D로 나타내면 모든 화살표의 출발점이 도착점보다 먼저 오는 순서를 찾을 수 있습니다. 이것이 위상 정렬입니다.
방향 비순환 그래프에는 이런 순서가 존재합니다. B와 C 사이에는 의존이 없으므로 [A,B,C,D]와 [A,C,B,D]는 둘 다 올바릅니다. 정답이 한 배열로 유일하다는 가정부터 버려야 합니다.
남은 선행 조건과 진입 차수
배포 D가 기다리는 작업은 B와 C, 모두 두 개입니다. 각 작업에 이렇게 ‘아직 앞에 놓아야 할 작업 수’를 적어 두면 다음 작업을 고르기 쉬워집니다. 그래프에서는 노드로 들어오는 간선 수를 진입 차수라고 부릅니다.
처음에는 A만 기다릴 작업이 없습니다. A를 결과에 넣으면 B와 C의 선행 조건이 하나씩 해결되어 둘 다 준비됩니다. 이제 B를 고르더라도 D는 바로 준비되지 않습니다. C가 아직 남아 있기 때문입니다. C까지 결과에 넣어야 D의 남은 조건 수가 0이 됩니다.
이처럼 진입 차수가 0인 노드를 꺼내고, 그 노드가 가리키는 후속 노드들의 차수를 하나씩 줄이는 방법이 Kahn 알고리즘입니다. 아래 그림과 표는 같은 예제를 각각 의존 관계와 처리 순서로 보여 줍니다.
그림을 글로 읽기
- A · 설정: 진입 차수 0
- B · 빌드: 진입 차수 1
- C · 데이터 준비: 진입 차수 1
- D · 배포: 진입 차수 2
- A · 설정 → B · 빌드: 먼저
- A · 설정 → C · 데이터 준비: 먼저
- B · 빌드 → D · 배포: 선행 조건
- C · 데이터 준비 → D · 배포: 선행 조건
| 처리 | 남은 B·C·D 차수 | 준비 큐 |
|---|---|---|
| 시작 | 1·1·2 | [A] |
| A 제거 | 0·0·2 | [B,C] |
| B 제거 | 제거·0·1 | [C] |
| C 제거 | 제거·제거·0 | [D] |
| D 제거 | 모두 제거 | [] |
B를 제거한 것만으로 D를 넣으면 C 의존을 놓칩니다. 차수를 0으로 만드는 마지막 선행 간선이 제거됐을 때만 준비 상태가 됩니다.
정렬과 입력 검증의 슈도코드
topologicalOrder(vertices, edges):
require all edge endpoints belong to vertices
edges = deduplicate(edges) # 단순 의존 관계 정책
outgoing = adjacency_list(vertices, edges)
indegree[v] = 0 for all vertices
for (u,v) in edges:
indegree[v] += 1
ready = FIFO(all vertices with indegree 0, stable initial order)
order = []
while ready not empty:
u = ready.pop_front()
order.append(u)
for v in outgoing[u] in stable order:
indegree[v] -= 1
if indegree[v] == 0:
ready.push_back(v)
if length(order) != length(vertices):
return cycle_blocked(order, vertices minus order)
return order
중복 간선을 허용한다면 차수 계산과 제거에서 동일한 중복 개수를 처리해야 합니다. 여기서는 의존 관계를 집합으로 취급해 먼저 제거합니다. 자기 의존 A→A는 차수가 0이 되지 않으므로 오류로 드러납니다.
인접 리스트와 FIFO를 사용하면 O(V+E) 시간, O(V+E) 저장 공간입니다. 매번 준비된 노드 중 가장 작은 ID를 선택하려면 최소 힙을 사용할 수 있으며 O(E+V log V) 정도로 비용이 달라집니다. 안정적인 초기·이웃 순서의 FIFO는 재현 가능한 순서를 주지만 사전순 최소 결과까지 주지는 않습니다.
선택 기준은 요구사항으로 고정합니다. 단순히 유효한 순서면 FIFO Kahn을 쓰고, 항상 가장 작은 ID가 필요하면 최소 힙을 쓰며, 순환 경로 설명이 필요하면 Kahn의 잔여 집합 뒤에 DFS나 SCC를 추가합니다. 한 알고리즘이 유효성·결정성·원인 설명을 모두 같은 비용으로 제공한다고 가정하지 않습니다.
순환 원인과 차단 노드의 구분
A→B, B→A, B→C에서는 처음부터 진입 차수 0인 노드가 없어 Kahn 결과에 세 노드가 모두 남습니다. 하지만 C에서 A나 B로 되돌아가는 경로는 없습니다. C는 B를 직접 기다리고 A에도 간접적으로 의존하지만, 순환 자체에 참여하지는 않습니다. 따라서 실제 순환의 원인은 A와 B이고 C는 순환 때문에 실행되지 못한 차단 노드입니다.
순환 경로를 직접 보여 주려면 DFS에서 A를 진행 중으로 표시한 뒤 B로 내려가고, B→A를 읽는 순간 진행 중인 A로 되돌아왔다는 사실을 기록할 수 있습니다. 또는 강한 연결 성분을 구해 여러 노드가 서로 도달하는 성분과 자기 간선이 있는 단일 노드를 순환 원인으로 봅니다. Kahn 뒤에 남은 목록 전체를 서로 순환한다고 표시하면 C까지 잘못된 원인으로 보고하게 됩니다.
정렬 결과와 실제 실행 성공의 분리
정렬에서 B를 order에 넣은 것은 B 실행이 성공했다는 뜻이 아닙니다. 실제 배포 실행기는 B·C 완료를 관찰한 뒤 D를 시작해야 합니다. 실패·취소·재시도·부분 결과와 이미 실행된 외부 효과를 따로 관리합니다.
순환이 있는 그래프에서 독립 작업만 먼저 실행할 수도 있지만, 설정 오류를 발견한 뒤 일부 외부 효과가 생기는 비용을 고려해야 합니다. 전체 유효성 검사가 먼저 필요한 배포라면 순서를 완전히 검증한 뒤 실행합니다. 정렬 중에 바로 외부 명령을 실행하는 코드는 이 판단을 숨기기 쉽습니다.
화살표 방향과 선행 조건 검증
정렬 결과의 각 노드 위치를 맵으로 만들고 모든 u→v에 대해 position[u] < position[v]인지 검사합니다. 같은 간선 목록 하나와만 비교하지 않습니다. 고립 노드와 여러 연결 성분도 결과에 한 번씩 들어가야 합니다.
순환 입력에서는 A·B와 그에 막힌 C를 구분하고, 자기 간선·중복 간선·없는 끝점·빈 그래프를 시험합니다. 마지막으로 실제 실행 테스트에서 선행 작업이 실패했을 때 후속이 시작되지 않는지 확인해 그래프의 정합성과 실행 상태의 정합성을 따로 검증합니다.
예상 결과를 고정한 작은 시험은 A→B, B→A, B→C에서 결과 길이가 0이고, 순환 원인은 {A,B}, 차단 노드는 {C}가 되는지 확인합니다. A→B, A→B를 집합 정책으로 넣으면 한 간선으로 정규화되고, 다중 간선 정책이면 두 차수를 모두 감소시켜야 합니다.