위상 정렬

위상 정렬(Topological Sorting, Topology Sort)은 방향 비순환 그래프(DAG, Directed Acyclic Graph)에서 노드들을 선형 순서로 정렬하는 알고리즘이다. 이 순서는 모든 간선 (u, v)에 대해 정렬된 결과에서 u가 항상 v보다 앞에 오도록 보장한다. 위상 정렬은 그래프가 순환이 없을 때만 가능하며, 주로 작업 스케줄링, 컴파일러에서의 의존성 분석, 데이터 흐름 최적화 등에 사용된다.

1 개요

위상 정렬은 방향 비순환 그래프(DAG)에서만 수행할 수 있으며, 그래프의 정점들을 특정한 순서대로 나열하여, 모든 간선이 순서에 맞게 정렬되도록 하는 것이다. 위 결과에서 보듯이 "위상이 정렬된 그래프"는 여러 가지로 만들어질 수 있다. 즉 정답이 하나만 있는 것은 아니다.

대표적인 위상 정렬 알고리즘은 다음과 같다.

• 칸 알고리즘(Kahn's Algorithm): 진입 차수를 이용하여 정렬하는 방식
• DFS 기반 위상 정렬: 후위 순회(postorder traversal) 방식으로 정렬

2 동작 방식 및 예제

위상 정렬은 다음 두 가지 방법으로 구현할 수 있다.

2.1 1. 칸 알고리즘 (Kahn's Algorithm)

칸 알고리즘은 노드의 진입 차수(in-degree)를 기반으로 동작한다.

• 1. 모든 노드의 진입 차수를 계산한다.
• 2. 진입 차수가 0인 노드를 큐에 추가한다.
• 3. 큐에서 노드를 꺼내며, 해당 노드와 연결된 간선을 제거한다.
• 4. 이 과정을 반복하면서 새로운 진입 차수가 0이 된 노드를 계속 큐에 추가한다.
• 5. 모든 노드를 방문하면 정렬이 완료된다.

예제

다음 방향 그래프를 예로 들어 보자.

 5 → 0 → 2  
 5 → 1 → 2  
 4 → 1  
 4 → 3 → 2  
 3 → 1  

1. 모든 노드의 진입 차수를 계산한다.
   • 0: 1개 (5 → 0)
   • 1: 2개 (5 → 1, 3 → 1)
   • 2: 3개 (0 → 2, 1 → 2, 3 → 2)
   • 3: 1개 (4 → 3)
   • 4: 0개
   • 5: 0개

1. 진입 차수가 0인 노드를 큐에 추가한다 → [4, 5]
2. 4를 꺼내고 3의 진입 차수를 감소 → 3의 진입 차수가 0이 됨 → 큐에 추가 → [5, 3]
3. 5를 꺼내고 0, 1의 진입 차수를 감소 → 0과 1의 진입 차수가 0이 됨 → 큐에 추가 → [3, 0, 1]
4. 3을 꺼내고 2의 진입 차수를 감소 → 2의 진입 차수가 0이 됨 → 큐에 추가 → [0, 1, 2]
5. 모든 노드를 방문하여 정렬 완료: [4, 5, 3, 0, 1, 2]

2.2 2. DFS 기반 위상 정렬

DFS를 수행하며 후위 순회를 이용하여 노드를 정렬하는 방식이다.

• 1. 방문하지 않은 모든 노드에서 DFS를 시작한다.
• 2. DFS 탐색이 끝나는 순서대로 노드를 스택에 추가한다.
• 3. 스택의 역순으로 정렬된 결과를 얻는다.

예제

다음 방향 그래프를 사용한다.

 5 → 0 → 2  
 5 → 1 → 2  
 4 → 1  
 4 → 3 → 2  
 3 → 1  

DFS를 수행하면:

1. 5에서 DFS 시작 → 0 방문 → 2 방문 후 스택에 추가 → 0 스택에 추가
2. 5에서 1 방문 → 2는 이미 방문 → 1 스택에 추가 → 5 스택에 추가
3. 4에서 DFS 시작 → 3 방문 → 1은 이미 방문 → 3 스택에 추가 → 4 스택에 추가

스택의 역순으로 정렬하면: **[4, 5, 3, 0, 1, 2]**

이제 실제 코드로 확인할 수 있다.

3 코드 예제

from collections import deque

def kahn_topological_sort(graph, n):
    in_degree = {i: 0 for i in range(n)}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in in_degree if in_degree[node] == 0])
    top_order = []

    while queue:
        node = queue.popleft()
        top_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return top_order if len(top_order) == n else []

# 예제 그래프
graph = {
    5: [0, 1],
    4: [1, 3],
    3: [1, 2],
    0: [2],
    1: [2],
    2: []
}

# 위상 정렬 실행
print(kahn_topological_sort(graph, 6))

출력 결과 예시:
[4, 5, 3, 0, 1, 2]

각 숫자는 정점이며, 위상 정렬된 순서를 나타낸다.

4 시간 복잡도

위상 정렬의 시간 복잡도는 O(V + E)이다.

• 칸 알고리즘: 각 노드를 한 번 방문하고, 간선을 한 번씩 처리하므로 O(V + E)
• DFS 기반 방법: 모든 노드를 방문하고 간선을 처리하므로 O(V + E)

5 응용

• 작업 스케줄링 (예: 강의 선수 과목 정렬)
• 컴파일러에서 의존성 분석
• 데이터 흐름 최적화
• 회로 설계에서의 신호 흐름 정리

6 같이 보기

• 깊이 우선 탐색
• 강한 연결 요소
• 그래프 이론

7 참고 문헌

• Kahn, Arthur B. "Topological sorting of large networks." Communications of the ACM 5.11 (1962): 558-562.