DAG(Directed Acyclic Graph) : 사이클이 없는 방향 그래프. DAG에서 에지 가 있다면 정점 u는 정점 v를 선행함. 위상 정렬(topological sort) : 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 순서대로 나열하는 것. 선행관계가 없는 것은 뭐가 먼저 나오든지 상관이 없기 때문에 위상 정렬 결과는 여러 가지가 존재할 수 있음. ▷ 알고리즘 1. 진입차수가 0인 임의의 정점(선행자가 없는 정점)을 큐(혹은 스택)에 삽입 2. 정점 개수만큼 시행하는 반복문 생성 3. 반복문 내부에서는, 큐에서 정점을 하나씩 꺼내어 출력하고 출력한 정점에 붙어있는 에지들을 제거하여 진입차수 재계산 4. 진입차수를 재계산하여 진입차수가 0이 된 것은 큐에 삽입 위상정렬이 불..
