위상 정렬

[Algorithm] 위상 정렬(Topological sort) 알고리즘

Topological sort 위상 정렬이란, 사이클이 없는 방향 그래프(DAG)를 방향성에 거스르지 않도록 순서대로 나열하는 것입니다. 대표적인 예시로, 선수 과목을 고려해서 학습 순서를 설정하는 것이 있습니다. 일반화학, 유기화학1, 유기화학2 라는 3과목이 있을 때, 아래의 학습 순서들 중 적절한 순서는 (2)가 될 것입니다. (1) 일반화학 -> 유기화학2 -> 유기화학1 (2) 일반화학 -> 유기화학1 -> 유기화학2 우선, 비순환 방향 그래프(DAG)에 대해 정리하겠습니다. 비순환 방향 그래프 (Directed Acyclic Graph) 위와 같이 방향 그래프이면서 사이클이 없는 그래프를 DAG라고 한다. DAG와 Topological sort 위상 정렬은 이러한 비순환 방향 그래프에서 정점들..