위상 정렬(Topological Sort)

위상 정렬(Topological Sort)이란?

위상 정렬(Topological Sort)은 방향 비순환 그래프(Directed Acyclic Graph, DAG)에서 정점들을 방향을 거스르지 않도록 순서대로 정렬하는 방법입니다. 작업 간에 순서가 정해져 있는 경우에 그 순서를 정해주는 방법이라고 생각할 수 있습니다.
대표적으로 대학 선수과목(prerequisite) 구조가 있습니다.

위와 같이 선이수를 해야 들을 수 있는 과목이 섞여있는 커리큘럼이 있다고 하자. 이때 전기기기를 듣기 위해서는 전자기학2와 회로이론2를 수강해야 한다. 또한 각각의 2과목을 듣기 위해서는 1과목을 들어야 하고 가장 먼저 미분적분학을 들어합니다.

따라서 미분적분학 → 전자기학1 → 회로이론1 → 전자기학2 → 회로이론2 → 전기기기 순서로 들어야 전기기기를 듣는것이 가능합니다.
물론 꼭 위와 같은 순서일 필요는 없습니다. 전자기학1 이 항상 전자기학2 보다만 앞에 오면 되고 회로이론1 이 항상 회로이론2 보다만 앞에 오면 되기 때문에 미분적분학 → 전자기학1 → 전자기학2 → 회로이론1 → 회로이론2 → 전기기기 이와 같은 순서도 가능합니다.

즉 정답이 유일하지는 않다는 것을 알 수 있습니다. 이러한 순서를 정하는 방법을 위상 정렬(Topological Sort)이라고 합니다.

 

작동 방식

모든 간선 (u → v)에 대해 u가 v보다 먼저 나오는 순서를 찾는 방식으로 진해됩니다.

위상 정렬의 대표적인 방법은 "queue를 사용하는 Kahn’s Algorithm"과 "DFS 기반 방법" 두 가지입니다.

Kahn’s Algorithm

1. 모든 정점의 진입 차수(in-degree)를 계산
   • 진입 차수(in-degree): 해당 정점으로 들어오는 간선의 개수
2. 진입 차수(in-degree)가 0인 정점을 큐에 삽입
3. 큐에서 정점을 하나씩 꺼내면서 연결된 간선 제거
   • 연결된 정점들의 진입 차수를 감소시키고,
   • 감소 후 진입 차수가 0이 되면 큐에 삽입
4. 모든 정점을 방문할 때까지 반복

✅ 시간 복잡도: $O(V + E)$ → 모든 간선과 정점을 한 번씩 처리

자세한 과정과 구현은 해당 링크 확인

위상 정렬(Topological Sort) - Kahn’s Algorithm

DFS 기반 위상 정렬

1. 방문하지 않은 정점에서 DFS 실행
2. DFS 종료 시점(재귀 탈출 시점)에서 스택에 삽입
3. 모든 정점을 탐색한 후 스택에서 꺼내면서 정렬된 결과 출력

✅ 시간 복잡도: $O(V + E)$ → DFS 탐색 한 번

자세한 과정과 구현은 해당 링크 확인

위상 정렬(Topological Sort) - DFS

위상정렬의 특징

• 시간 복잡도: $O(V+E)$
• 방향 비순환 그래프(DAG, Directed Acyclic Graph)에서만 적용 가능 (순환이 있으면 위상 정렬 불가능)
• 정렬된 순서는 유일하지 않을 수 있음 → 위상 정렬 결과가 여러 개 존재할 수 있음
• 작업 스케줄링, 의존성 해결 등에서 활용

위상 정렬을 사용하기 좋은 경우

1. 작업 간에 순서가 정해져 있는 경우 → 선이수과목
2. 서로 의존성이 있는 모듈을 어떤 순서로 실행할지 결정해야 하는 경우