위상 정렬 (Topological Sorting)

• 정렬 알고리즘의 일종
• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용
• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

진입차수와 진출차수

• 진입차수 (Indegree): 특정한 노드로 들어오는 간선의 개수
• 진출차수 (Outdegree): 특정한 노드에서 나가는 간선의 개수

위상 정렬 알고리즘 동작 과정

1. 진입 차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
  a. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
  b. 새롭게 진입차수가 0이 된 노드를 큐에 삽입

⇒ 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과

위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG) 여야만 한다.

위상 정렬의 특징

• 위상 정렬은 사이클이 없는 방향 그래프(DAG) 에 대해서만 수행할 수 있다.
• 위상 정렬에는 여러 가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재할 수 있다는 의미이다.
• 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다.
• 보통 큐를 사용하나 스택을 이용한 DFS로도 구현이 가능하다.
• 시간 복잡도는 O(V + E)
  • 차례대로 모든 노드(V)에 대해, 해당 노드에서 출발하는 간선(E)을 차례대로 제거해야 하기 때문이다.

Reference

https://velog.io/@kimdukbae/위상-정렬-Topological-Sorting