[Algorithms] Topological Sort

이해하기 쉽게 받아들이자면, 자신에게 들어오는 edge가 없는 순서대로 정렬하는 것이다.
즉, 자신에게  dependency가 없는 순서대로 정렬한다!

사이클이 있을 경우 topological sort가 존재하지 않는다.

당연하다! 사이클이 있다는 것은 서로 의존성이 있는 것일테니까~

사용되는 예로는 Compiler의 Syntax directed Translation에서 각 attribute의 dependency를 구하는 데 사용한다.
그 순서대로 attribute가 계산되는 순서를 정한다.

어떠한 그래프에 대해 여러 개의 topological sort가 존재 가능하다.

아래의 그림에서 다음과 같은 sort가 가능하다.

• 7, 5, 3, 11, 8, 2, 9, 10
• 3, 5, 7, 8, 11, 2, 9, 10
• 3, 7, 8, 5, 11, 10, 2, 9
• 5, 7, 3, 8, 11, 10, 9, 2
• 7, 5, 11, 3, 10, 8, 9, 2 
• 7, 5, 11, 2, 3, 8, 9, 10