개념

<aside> 💡 순서가 정해져 있는 일련의 작업을 차례로 수행해야 할 때 순서를 결정하기 위해 사용하는 알고리즘

</aside>

위상정렬 개념 및 특징

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

위상 정렬 알고리즘은 큐를 이용하여 구현

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

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

특징

1. 사이클이 없는 방향 그래프에서만 수행 가능
2. 여러 답이 존재할 수 있다. (큐에 들어가는 원소가 2개 이상이라면 여러 답 존재 가능)
3. 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 ㅍ ㅏㄴ단
4. 큐 or 스택을 이용한 dfs 를 통해 구현 가능

위상정렬 원리와 동작과정

위상 정렬을 수행하려면 사이클이 없는 방향그래프여야 한다.