비순환 방향 그래프 (Directed Acyclic Graph)

DAG라고 부르는 비순환 방향 그래프는 사이클이 없는 방향 그래프이다. DAG은 주로 이벤트간의 우선순위를 나타낼 때 사용한다.

사이클이 있으면 DAG이 아니므로 주의해야 한다.

위상 정렬 (Topological sort)

위상 정렬이란 비순환 방향 그래프에서 정점을 선형으로 정렬한 것이다. 그래프를 선형으로 정렬하면 그림과 같이 정점에 대해 선후관계가 생긴다. 따라서 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

• 위상 정렬 결과 하나의 DAG에서 하나 이상의 위상 순서(Topological order)가 나올 수 있으며 모든 간선은 오른쪽만 가리킨다.

사이클

주의할 점으로는 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능하다. 그래프에 사이클이 있고 두 정점 u,v가 사이클 내에 위치한 정점일 경우, 정점 u가 v보다 먼저 오거나 v가 u보다 먼저 올 수 있기 때문에 두 정점 u, v에 대한 선후관계가 정확하지 않아 문제가 생기기 때문이다.

또한 사이클이 있으면 시작점을 무엇으로 잡아야 할지 찾을 수 없으므로 주의해야 한다.