사이클이 없는 방향 있는 그래프를 DAG라고 한다.
간선에 방향이 있음
상당히 많이 등장하는 그래프이다.
어떤 일이 있을 때, 1번 일을 해야 2번 일을 할 수 있는 선행관계가 있을 때를 표현할 수 있기 때문
예를들어 1번 스킬을 찍어야 4번 스킬을 찍을 수 있다.
근데 4번은 1번과 2번을 찍어야하니 4번은 1,2번을 찍어야 스킬을 찍을 수 있다.
또는
1,2 번 수업을 들어야 4번 수업을 들을 수 있다, 1,2번 옷을 입어야 4번 옷을 입을 수 있다.등등
어떤 것을 뭔가 해야하는 상황을 그래프로 표현하면 DAG로 표현할 수 있다.
그래서 상당히 중요한 그래프
DAG에서는 위상 정렬이라는 알고리즘을 이용해서 순서를 찾게 된다.
여기서 순서는 뭐냐면 어떤 정점을 순서대로 했을 때 선행관계에 대한 관계를 모두 지킬 수 있는지 알아보는 것