[[분류:알고리즘]]
[include(틀:이론 컴퓨터 과학)]
[[파일:Q3MA6dZ.png|align=right]]
[목차]
[clearfix]
== 개요 ==
{{{+2 Topological Sort / Topological Ordering}}}

순환하지 않는 유향 그래프를 방향성에 거스르지 않도록 순서대로 배열하는 방법.
== 정의 ==
부분 순서 집합 [math(\left(A,\preceq\right))]에 대해, 이를 [math(\forall a,b\in A(a\preceq b\to a\preceq_T b))] 를 만족하는 전순서 관계 [math(\left(A,\preceq_T\right))] 를 생각할 수 있으며 이와 같이 어떤 부분 순서 관계와 호환되는(compatible)[* 즉 [math(\preceq)]는 [math(\preceq_T)]의 부분 집합이라고 할 수 있으며 이를 만족하는 [math(\preceq_T)]는 경우에 따라 무수히 많이 존재할 수 있다. 따라서 위상 정렬은 일반적으로 주어진 입력에 대해 조건을 만족하는 여려 결과가 나올 수 있다.] 전순서 관계를 만드는 과정을 [math(A)]의 위상 정렬이라고 한다.

모든 유한 부분 순서 집합은 유향 그래프 [math(G=(V,E))]로 나타낼 수 있으므로, 해당 그래프에서 모든 [math(e\in E)] 인 모든 [math(e=(u,v))]에 대해 [math(u)]가 [math(v)]보다 앞에 위치하도록 만드는 과정을 유향 그래프 [math(G)]의 위상 정렬이라고 한다.
=== 조건 ===
위상 정렬이 가능하려면 해당 그래프는 방향이 있고 순환하지 않는 그래프(Directed Acyclic Graph)여야 한다. (흔히 줄여서 DAG로 부른다)

무향 그래프라면 정렬이 의미가 없고 순환하는 그래프라면 위상 정렬이 불가능하다. 이는 사이클을 부분 그래프로 가지는 경우 후술한 진입차수가 절대 0이 되지 않는 구간이 발생하기 때문.
=== 비전공자를 위한 설명 ===
간단한 비유로, 지금부터 [[라면]]을 준비한다고 생각해보자. 라면을 요리하는 단계는 '사리 부수기', '스프 넣기', '끓이기', '밥 준비하기', '사리 넣기', '물 넣기', 등 여러 가지 작업으로 나눌 수 있을 것이다. 순서가 뭔가 이상하다고 느꼈다면 정상이다. 우선 필수적인 순서부터 정리해보자. 물을 넣기 전에 스프나 사리부터 넣을 수는 없다. 물을 넣기 전에 끓이는 것 역시 불가능하다. 사리를 넣고 나서는 부술 수 없다.[* 사리를 부수냐 그대로 넣냐는 취향에 따라 갈리지만 본 예시에서는 복잡한 그래프를 만들기 위해 부수는 단계를 필수로 가정한다.] 하지만 스프를 먼저 넣냐 사리를 먼저 넣냐는 큰 상관이 없다. 끓이기 역시 마찬가지다. 밥 준비하기는 라면 준비와는 아예 별도의 독립적인 과정이다.

[[파일:toposort-example.svg]]

이러한 부분적인 순서 관계만 있는 상황에서, 요리를 하는 사람은 자신이 원하는 대로 전체 레시피를 완성할 수 있다. 예를 들어 {{{물 넣기 → 스프 넣기 → 끓이기 → 사리 부수기 → 사리 넣기 → 밥 준비하기}}} 도 가능하며 {{{사리 부수기 → 물 넣기 → 사리 넣기 → 밥 준비하기 → 스프 넣기 → 끓이기}}} 도 ~~[[멀티태스킹]]이 된다면~~ 가능하다. 하지만 {{{끓이기 → 스프 넣기 → 사리 넣기 → 밥 준비하기 → 물 넣기 → 사리 부수기}}} 와 같은 레시피는 올바른 라면을 만들 수 없다. 앞서 정의한 순서를 위반하기 때문이다. 이와 같이 주어진 순서 조건들을 만족시키도록 정렬하는 행위를 '위상 정렬'이라고 이해하면 좋다.
== 알고리즘 ==
크게 Kahn 알고리즘과 DFS로 나눌 수 있으며, 두 알고리즘 모두 [math(\mathcal{O}(V+E))]의 [[시간복잡도]]를 지닌다.

이 두 알고리즘을 이해하려면 진입차수와 진출차수에 대해 알아야 한다.
 * [[그래프(이산수학)#s-2.4.3|진입차수: 어떤 노드 N으로 향하는 간선의 개수]]
 * [[그래프(이산수학)#s-2.4.3|진출차수: 어떤 노드 N에서 다른 노드로 향하는 간선의 개수]]

두 알고리즘 모두 진입차수가 0인 노드를 엣지와 함께 순서대로 제거하는 방식으로 이루어진다.

이 때, 순환하지 않는 유향 그래프가 진입차수가 0인 노드를 반드시 하나 이상 포함한다는 사실은 증명되어 있기 때문에 시작점으로 사용할 노드 S를 고른다.
=== Kahn 알고리즘 ===
 1. 진입차수가 0인 노드를 전부 큐 Q에 집어넣는다.
 1. 큐에서 노드 하나를 뽑아 해당 노드가 가리키는 모든 노드의 진입차수를 1씩 줄인다.
 1. 큐가 빌 때까지 2를 반복한다.
 1. 그래프가 완전히 비지 않았다면 1로 돌아간다.

이때 최종적으로 Q에서 빠져나간 순서가 위상 정렬된 순서가 된다.
==== 의사 코드 ====
{{{Q가 빌 때까지 반복:
    Q에서 v를 뽑는다.
    v를 L에 추가한다.
    v에서 출발하는 모든 간선 e에 대해:
        e의 도착지 u의 진입차수를 1 내린다.
        만약 u의 진입차수가 0이라면:
            u를 Q에 추가한다.
}}}
=== [[DFS]] ===
 1. 임의의 노드 S를 고른다.
 1. DFS로 그래프를 탐색하며 진출차수가 0인 노드에서 멈춘다.
 1. 해당 노드를 스택에 넣는다.
 1. 2로 돌아가 다시 거슬러 올라가 탐색한다.
 1. 만약 더이상 갈 수 있는 곳이 없다면 다시 임의의 노드 S2를 골라 2로 돌아간다.
 1. 그래프가 빌 때까지 반복한다.

이때 노드를 스택에서 뺀 순서가 위상 정렬된 순서가 된다.
== 활용 ==
 * 작업 스케줄링, 종속성 처리
 여러 작업들이 서로 먼저 처리해야 하는 종속성을 가지고 있는 경우 가장 활용하기 좋다. [[Make]]와 같은 빌드 시스템, [[npm]]등의 패키지 매니저, [[운영체제]]의 [[프로세스 스케줄링]]까지 다양한 분야에서 활용된다.
  * 데이터 직렬화
  만약 직렬화 하려는 한 객체가 다른 객체에 대한 참조를 가지고 있다면, 시리얼라이저는 이 종속성 관계를 파악해 가장 안쪽 객체부터 차례대로 처리한다.[* When serializing data objects that have dependencies on each other, topological sorting can be used to ensure that each object is serialized after its dependencies.]
 * 부분 정렬
 만약 주어진 데이터가 항상 서로 비교 가능하다면 [[정렬 알고리즘]]을 사용할 수 있지만, 데이터에 비교된 값의 일부만 포함된 경우 또는 소실된 경우, 위상 정렬을 사용해 주어진 조건을 만족하는 정렬된 상태를 찾을 수 있다.
 * 심볼 추적
 [[컴파일러]]가 소스 코드를 파싱하고 심볼 테이블을 작성할 때, 한 심볼이 다른 심볼에 대한 참조를 가질 수 있다(class 등의 경우.) 이 때 심볼 테이블을 그래프로 만들고 위상 정렬을 통해 테이블 순서를 재정렬하는 과정을 거친다.
 * 사이클 감지
 사이클이 존재하는 그래프는 위상 정렬이 반드시 실패한다는 점을 역으로 이용해 주어진 그래프가 순환하는지 여부를 검증하는 데에도 사용할 수 있다. 흔히 [[데드락]] 등 교착 상태에서의 사이클을 감지하고 해결하기 위해 사용된다.
== 관련 문서 ==
 * [[그래프(이산수학)]]
 * [[순서 관계]]
 * [[하세 다이어그램]]