위상 정렬

유향 비순환 그래프 (DAG = Directed acyclic graph) 와 Khan 알고리즘을 이용한 위상 정렬 (Topological Sort)

DAG에 대한 토폴로지 정렬 알고리즘 위상 정렬이란 방향이 있는 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점들을 나열하는 것이다. 싸이클이 없는(DAG, Directed Acyclic Graph) 그래프에선 가능하며 하나의 유향 그래프에서 여러 위상 정렬이 가능하다. 시간 복잡도 : O(V + E) / V (Vertex) : 노드, E (Edge) : 간선 => Best Case, Worst Case 동일. DFS와 관련된 다양한 유형의 에지의 출발 시간 사이의 관계이다. Tree edge (u, v): departure[u] > departure[v] Back edge (u, v): departure[u] < departure[v] Forward edge (u, v): dep..