위상 정렬

• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘

• 방향 그래프의 모든 노드를 '방향성에에 거르지 않도록 순서대로 나열하는 것'이다.

• 대표적인 예시로는 선수과목을 고려한 학습 순서 설정이 있다.

위상정렬 동작 과정

• 진입차수 :
  특정한 노드로 '들어오는' 간선의 개수를 의미한다.

1. 진입차수가 0인 노드를 큐에 넣는다.

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

위상정렬 동작 예시

• 위상정렬을 수행할 그래프
  여기서는 사이클이 발생하는 경우는 고려하지 않는다.
  

0. 초기 단계에서는 진입차수가 0인 노드를 큐에 넣는다.
   처음에 노드1을 큐에 삽입한다.
   

1. 큐에서 노드 1들 꺼낸 뒤 노드 1과 연결되어 있는 간선들을 제거한다.
   새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다.
   

2. 큐에서 노드 2를 꺼낸 뒤에 노드 2에서 나가는 간선들을 제거한다.
   새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다.
   

3. 큐에서 노드 5를 꺼낸 뒤에 노드 5에서 나가는 간선들을 제거한다.
   새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다.
   

4. 큐에서 노드 3를 꺼낸 뒤에 노드 3에서 나가는 간선들을 제거한다.
   새롭게 진입차수가 0이 된 노드가 없으므로 그냥 넘어간다.
   

5. 큐에서 노드 6를 꺼낸 뒤에 노드 6에서 나가는 간선들을 제거한다.
   새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다.
   

6. 큐에서 노드 4를 꺼낸 뒤에 노드 4에서 나가는 간선들을 제거한다.
   새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다.
   

7. 큐에서 노드 7를 꺼낸 뒤에 노드 7에서 나가는 간선들을 제거한다.
   새롭게 진입차수가 0이 된 노드가 없으므로 그냥 넘어간다.
   

위상정렬 결과

• 큐에 삽입된 전체 노드 순서 : 1 - 2 - 5 - 3 - 6 - 4 - 7

위상정렬 소스코드

위상정렬

위상정렬의 시간 복잡도

• $O(V + E)$
  위상 정렬을 수행랄 때는 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거해야 한다.
  결과적으로 노드와 간선을 모두 확인한다는 측면에서 $O(V + E)$의 시간이 소요되는 것이다.

출처 : 이것이 코딩테스트다. with 파이썬