[개념] 위상 정렬(Topological Sort)

# 위상 정렬이란?

순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘

• 선후 관계가 정의된 그래프
• 위상 정렬이 성립하기 위해서는 방향 비순환 그래프이어야 한다.

오른쪽의 경우 순환이기 때문에 위상 정렬 불가능

# 흐름

0. 모든 정점의 진입 차수를 계산한다.

• 진입 차수(in-degree) : 자신으로 들어오는 간선의 수

1. 진입 차수가 0인 정점을 모두 큐에 넣는다.

• 진입 차수가 0인 정점 = 시작점

• 위 경우에서는 A, E가 큐에 들어가게 된다.

2. 큐에서 정점을 꺼내어 해당 정점과 인접한 정점의 간선을 제거하고 인접한 정점의 진입 차수를 1 감소시킨다.

• 인접한 정점의 진입 차수가 1 감소 이후 0이 된다면 인접한 정점을 큐에 넣어준다.
• 큐가 빈 상태가 될 때까지 반복한다.

 

---

# 관련 문제

(2252 - 줄 세우기 풀이는 추후 업로드 예정~)

14567번: 선수과목 (Prerequisite)

2252번: 줄 세우기