위상 정렬 (Topology Sort)

위상 정렬이란

순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘

사이클이 발생하는 경우 위상 정렬을 수행할 수 없음
큐와 스택을 통해 구현 가능

위상 정렬 과정

1. 진입차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌 때까지 2번 ~ 3번 과정을 반복
4-1. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재
4-2. 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

시간 복잡도

O(V + E)