1. Topological Sort 번역하자면 위상정렬이다. *DAG: Directed Acyclic Graph (방향성이 있고 사이클이 없는 그래프) 위상 정렬은 DAG의 노드들을 왼쪽에서 오른쪽 방향(엣지 방향이 모두 오른쪽) 으로 정렬하는 것을 의미한다. DAG에 사이클이 존재하지 않으면 알고리즘은 항상 성공한다. 사이클이 없기 위해서는 indegree=0 인 노드가 최소 하나 이상 있어야한다. 이를 귀류법으로 증명해보겠다. indgree=0인 노드가 없다고 가정해보자. indgree=0인 노드를 안만들기 위해서는 계속 들어가는 노드를 만들어야하는데, 이 과정이 무한하게 흘러간다. 무한하지 않으려면 다른노드와 연결해야하는데 이렇게 되면 사이클이 생긴다. 1.1 algorithm DAG G에서 ind..