[알고리즘] 위상정렬

위상 정렬, topological sort

순서가 정해져있는 작업을 차례로 수행해야 할 때 사용

DAG(Directed Acyclic Graph)에만 적용 가능 / 사이클이 발생하지 않는 방향 그래프

시간 복잡도: O(V+E)/정점 개수 + 간선 개수 

 

예시> 대학의 선수과목(prerequisite)

만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다.

 

 

Queue로 구현

- 깊이가 0이 정점 큐에 삽입

- 큐에서 정점 꺼내서 연결된 모든 간선 제거

- 간선 제거하면서 방문한 정점은 깊이 1씩 감소

- 이후 깊이가 0인 정점 큐에 삽입 ~ 반복