위상정렬

위상 정렬(Topological Sort)? 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘으로, 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다. 실생활을 예로 들면, 인터넷 검색을 하기 위해선 다음과 같은 순서로 행동해야한다. 컴퓨터 전원 키기 -> 브라우저 키기 -> 검색 엔진 포털 진입 -> 검색 위 순서가 바뀐다면 검색을 할 수 없을 것이다. 위상 정렬은 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능하다. 여기서 주의할 점은 E가 수행되기 위해선 B와 D가 모두 수행되어야 한다는 점이다. 비순환 방향 그래프 (DAG: Di..