yoongrammer

목차 위상 정렬(Topological sort) 개념 및 구현비순환 방향 그래프 (DAG: Directed Acyclic Graph)Directed Acyclic Graph (DAG)는 사이클이 없는 방향 그래프입니다. DAG는 이벤트 간의 우선순위를 나타내기 위해 주로 사용됩니다. 위상 정렬(Topological sort)위상 정렬(Topological sort)은 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것입니다.모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 됩니다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능합니다.그래프에 사이클이 있으면서 두 정점 u,v가 사이클 속에 위치한 정점일 경우, 정점 u가 v보다 먼저 오거나 v가 u보다..