[Algorithm] Topology sort(위상 정렬)

위상정렬

위상정렬은 정렬 알고리즘의 일종이다. 이상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용 할 수 있는 알고리즘이다.  즉, 위상정렬은 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.

 

위상 정렬 알고리즘을 사용하기 위해서는 진입 차수(degree) 부터 알아야한다. 진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다. 진입차수를 이용하여 위상정렬을 하는 방법은 다음과 같다.

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

위상 정렬의 시간 복잡도는 O(V+E)이다. 위상 정렬을 수행 할 떄는 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발 하는 간선을 차례대로 제거해야 된다.