[정렬] 위상 정렬(Topological Sort)

위상 정렬은 사이클이 발생하지 않는 방향 그래프에서 사용한다.

순서를 결정할 때 사용하는 알고리즘으로, 순서가 정해져 있는 작업을 신경 쓴다.

 

 

https://m.blog.naver.com/ndb796/221236874984

 

 

위상 정렬은 아래처럼 동작한다.

 

 

1. 진입차수가 0인 정점(들)을 큐에 넣는다.

(진입차수란 상대 정점에서 자신의 정점으로 오는 간선의 수이다.)

 

2. 큐에 있는 원소를 꺼낸다. 

 

3. 진입차수가 0인 정점(들)을 큐에 삽입한다.

 

4. 큐가 빌 때까지 2~3번을 반복한다.

 

위상 정렬이 모든 원소를 방문했다면, 큐에서 꺼낸 순서가 결과이다.

(모든 원소를 방문하기 전에 큐가 빈다면,

사이클이 존재하는 것으로 위상 정렬을 사용할 수 없다.)

 

동작 방식을 보면 알 수 있듯이, 위상 정렬은 답이 여러 개가 될 수 있다.