**위상 정렬(Topology Sort)**은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 순서가 정해져있는 작업의 대표적인 예시는 다음과 같습니다.

그래프의 흐름은 사실 '조건'으로 해석할 수 있습니다. 일반적으로 정보처리기사를 취득하기 위해서는 반드시 '4학년 되기'를 만족을 해야 하고, 4학년이 되기 위해서는 그 전에 '대학생 되기'를 만족해야 합니다. 이렇게 작업의 순서가 정해져 있을 때 작업을 정확하게 정렬해주는 알고리즘이 필요할 수 있습니다. 위와 같이 여러 개의 순서가 정해져있을 때 조건에 부합하는 일직선의 순서를 찾아봅시다.  위상 정렬: 대학생 되기 -> 학과 사이트 가입하기 -> 4학년 되기 -> 정보처리기사 합격하기 -> 자격 서류 제출하기 -> 졸업시험 신청하기 -> 졸업하기  위와 같이 정렬을 하면 순서대로 작업을 수행했을 때 성공적으로 '졸업하기' 까지 갈 수 있습니다. 사실 위 답 말고도 다른 답도 존재합니다. 위상 정렬은 여러 개의 답이 존재할 수 있다는 점에서 매력적이죠 또한 위상 정렬은 **DAG(Directed Acyclic Graph)**에만 적용이 가능합니다. 이것은 사이클이 발생하지 않는 방향 그래프하는 의미입니다. 사이클이 발생하는 경우 위상 정렬을 수행할 수 없습니다.

위와 같은 그래프가 있다고 했을 때 이것을 위상 정렬할 수 있을까요? 불가능합니다. 위상 정렬은 시작점 존재해야 하는데 위와 같은 사이클 그래프에서는 시작점부터 찾을 수가 없습니다. 이제 한 번 위상 정렬을 수행하기 위해 맨 처음에 들었던 그래프의 정점을 숫자로 표기해보겠습니다.

위상 정렬 알고리즘은 두 가지 해결책을 낸다는 특징이 있습니다. ① 현재 그래프는 위상 정렬이 가능한지 ② 위상 정렬이 가능하다면 그 결과는 무엇인지입니다. 이러한 위상 정렬을 수행하는 알고리즘으로는 크게 두 가지가 존재합니다. 하나는 스택(Stack)을 이용한 방식이고, 다른 하나는 큐(Queue)를 이용한 방식입니다. 저는 기본적으로 스택보다는 큐를 선호하므로 큐를 이용하는 방법을 소개하겠습니다.  ① 진입차수가 0인 정점을 큐에 삽입합니다.  ② 큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다.  ③ 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입합니다.  ④ 큐가 빌 때까지 2번 ~ 3번 과정을 반복합니다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과입니다.

바로 시작해봅시다. 위와 같이 처음에는 각 정점과 진입차수 정보를 기입합니다.

위와 같이 진입차수가 0인 정점 1을 큐에 삽입합니다.

위와 같이 1을 큐에서 빼낸 뒤에 연결되어있던 간선을 다 제거해주었습니다. 이제 표를 봅시다.

따라서 진입차수가 0인 새로운 정점들을 다시 큐에 삽입해줍니다.

위와 같습니다. 이제 다시 큐에서 정점 2를 빼내면 됩니다.

빼낸 뒤 결과는 위와 같습니다. 이후에 연결된 간선을 제거한 뒤에 표를 다시 봅시다.