위상 정렬이란 정렬 알고리즘의 일종이다.
위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.
조금 더 이론적으로 설명하자면, 위상 정렬이란
방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것" 이다.
현실세계에서 위상 정렬을 수행하게 되는 전형적인 예시로는 "선수과목을 고려한 학습 순서 설정"을 들 수 있다.
예를들어 컴퓨터 공학과의 커리큘럼에는 '자료구조' 과목을 수강한 뒤에 '알고리즘' 강의를 수강하는 것을 권장한다.
이때 '자료구조' 및 '알고리즘'을 각각의 노드로 표현하고,
'자료구조'에서 '알고리즘'으로 이어질 수 있도록 방향성을 갖는 간선을 그릴 수 있다.
다시 말해서, 그래프상에서 선후 관계가 있다면 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.
예를들어 노드로 자료구조, 알고리즘, 고급알고리즘이 있고
선수과목의 관계가
자료구조 -> 알고리즘
알고리즘 -> 고급알고리즘
자료구조 -> 고급알고리즘 일때
진입차수(Indegree) == 특정한 노드로 들어오는 간선의 개수
고급알고리즘은 진입차수가 2개
알고리즘은 1개
자료구조는 0개이다.
이때 위상정렬 알고리즘은 다음과 같이 동작한다.
1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
* 이때 모든 노드를 방문하기전에 큐가 빈다면 사이클이 생겼다고 볼 수 있다.
출처: 이코테
