위상 정렬 Topological Sort

위상 정렬(Topological Sort)이란?

정렬 기준이 '위상'으로 여기서 위상이란 진입차수(incoming edge의 수)를 의미한다

 

위상 정렬의 특징

- Directed Acyclic Graph(DAG)에서만 가능

- 즉, 방향을 가지며 싸이클은 형성하지 않는 그래프를 말한다

- 보통 일의 순서를 정하는 알고리즘에서 많이 사용됨

 

위상 정렬 알고리즘

1. 각 노드의 위상(incoming edge의 수)를 저장
2. 위상이 0인 노드를 큐에 푸쉬
3. 큐가 빌 때까지 아래 과정 반복
   1. 큐에서 노드를 꺼내 해당 노드와 연결된 노드의 간선을 모두 제거(동시에 연결된 노드의 위상을 하나씩 낮춰줌)
   2. 큐에서 꺼낸 노드를 위상정렬에 넣어줌
   3. 위상이 0인 노드를 큐에 푸쉬