위상 정렬 (Topological Sort)

한 줄 정의: 방향 그래프에서 화살표가 가리키는 순서를 거스르지 않도록, 선행 작업이 항상 후행 작업보다 먼저 오도록 노드들을 한 줄로 나열하는 정렬 방법입니다.

쉽게 풀면

대학교 수강신청을 떠올려 보세요. "자료구조"를 들어야 "알고리즘"을 들을 수 있고, "알고리즘"을 들어야 "고급알고리즘"을 들을 수 있다면, 이 선후관계를 어기지 않는 수강 순서표를 만들어야 합니다. 위상 정렬은 바로 이렇게 여러 개의 '이것 다음에 저것' 규칙이 있을 때, 모든 규칙을 동시에 만족하는 하나의 순서를 찾아주는 방법입니다. 단, 이 방법은 순환(A가 B의 선행조건이면서 동시에 B가 A의 선행조건인 경우)이 없는 그래프에서만 가능합니다.

왜 중요한가

많은 실무·연구 시스템이 작업 간 의존 관계를 방향 비순환 그래프로 표현하기 때문에, 위상 정렬은 컴파일러의 빌드 순서 결정, 딥러닝 프레임워크의 연산 그래프 실행 순서, 스케줄링·프로젝트 관리 알고리즘의 기초 연산으로 폭넓게 쓰입니다. 그래프 알고리즘 논문에서는 이를 더 복잡한 문제(경로 최적화, 병렬 스케줄링 등)를 푸는 전처리 단계로 자주 활용합니다.

논문에서는 이렇게 쓰입니다

"작업 간의 선후행 종속성을 방향 비순환 그래프(DAG)로 모델링한 뒤, 위상 정렬(topological sort)을 수행하여 실행 가능한 작업 순서를 도출하였다."

이 문장은 여러 작업 사이에 "이 작업이 끝나야 저 작업을 시작할 수 있다"는 제약이 있을 때, 그 제약을 모두 지키면서 전체 작업을 처리할 수 있는 순서를 자동으로 계산했다는 뜻입니다. 빌드 시스템의 컴파일 순서, 프로젝트 일정 관리, 신경망 계층 연산 순서 결정 등에 널리 쓰입니다.

"신경망 연산 그래프를 위상 정렬하여 각 노드의 순전파 실행 순서를 결정함으로써, 하위 연산 결과가 준비되기 전에 상위 연산이 호출되는 것을 방지하였다."

딥러닝 프레임워크 내부에서 계산 그래프를 실행 가능한 순서로 배치할 때 위상 정렬이 활용되는 예시입니다.

"패키지 관리 시스템에서 의존성 그래프에 순환이 존재하지 않음을 위상 정렬 수행 여부로 검증하고, 정렬 결과를 설치 순서로 사용하였다."

소프트웨어 패키지 의존성 해석에서 위상 정렬이 순환 탐지와 설치 순서 결정을 동시에 수행하는 데 쓰이는 사례입니다.

조금 더 깊게 보면

위상 정렬을 구현하는 대표적인 방법은 진입 차수(in-degree)가 0인 노드부터 큐에 넣어 차례로 제거하는 칸(Kahn) 알고리즘과, 깊이 우선 탐색(DFS)이 끝나는 순서를 뒤집어 사용하는 방식 두 가지입니다. 두 방식 모두 시간 복잡도는 노드와 간선 수에 선형으로 비례하며, 순환이 존재할 경우 칸 알고리즘에서는 큐가 비기 전에 처리되지 않은 노드가 남고 DFS 방식에서는 역방향 간선이 검출되어 순환 여부를 함께 판별할 수 있습니다.

주의할 점

위상 정렬은 그래프에 순환이 존재하면 애초에 불가능하며, 같은 그래프라도 정답이 되는 순서가 하나가 아니라 여러 개일 수 있습니다. 크루스칼 알고리즘처럼 그래프에서 사이클 발생 여부를 빠르게 검사할 때는 유니온-파인드 자료구조가 함께 쓰이기도 합니다.