[알고리즘] 위상 정렬(Topological Sort)

0. 위상 정렬(Topological Sort)

위상 정렬은 유향 그래프의 정점들을 나열하는 것을 의미한다.

순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘으로 위상 정렬의 결과는 여러 개일 수 있다.

가장 잘 설명되는 예시로는 선수과목(prerequisite) 구조이다. 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 수강 순서를 찾아낼 수 있다.

위상 정렬이 성립하기 위해서는 그래프의 순환이 존재하지 않는 비순환 유향 그래프(directed acyclic pragh)여야 한다.

 

위상 정렬은 아래 2가지에 대한 판단이 가능하다.

1. 현재 그래프는 위상 정렬이 가능한지 → 사이클이 존재하지 않는지
2. 위상 정렬이 존재한다면 그 결과는 무엇인지

---

1. 알고리즘

위상 정렬은 BFS와 DFS로 모두 구현이 가능하다.

이번에는 큐를 이용한 BFS로 구현할 예정이다.

1. 진입 차수가 0인 정점을 큐에 모두 넣는다.
2. 큐에서 진입 차수가 0인 정점을 꺼내어 자신과 인접한 정점의 간선을 제거한다. → 인접한 정점의 진입 차수를 1 감소시킨다.
3. 큐가 공백이 될 때까지 1번부터 작업을 반복한다.
4.  모든 노드가 다 처리되었다면 위상 정렬 완성, 처리되지 않은 노드가 있다면 사이클 발생

---

2. 구현

2-1. 위상 정렬이 가능한 경우

2-2. 위상 정렬이 불가능한 경우(사이클이 발생한 경우)