DAG

Directed Acyclic Graph
사이클이 없는 방향 있는 그래프
선행 관계가 있다.

위상 정렬

오직 DAG 를 할 수 있는 알고리즘
그래프의 간선 u -> v 가 u가 v 가 먼저라는 의미일 때 정점의 순서를 찾는 알고리즘.

구현 방법

BFS

• 어떤 정점 v의 순서에 추가되는 것은 u → v의 u가 모두 순서에 추가되었을 때이다.
• 순서에 추가되는 정점은 in-degree가 0일 때로 표현할 수 있다.
• BFS를 응용해서 구현할 수 있다

DFS

• 위상 정렬은 DAG에서만 할 수 있고, DAG는 사이클이 없다.
• 그래프의 간선을 모두 뒤집어놓고 DFS를 수행하고 정점이 스택에서 빠져나오는 순서를 기록하면 위상 정렬의 순서와 같아지게 된다.
• 스택에서 빠져나온다는 것은 더 이상 방문할 수 있는 정점이 없다는 것을 의미하고, 방문할 수 있는 정점이 없다는 것은 이제 이 일을 수행할 수 있다는 것과 같은 의미이다.