방향을 따라 판단한다
A→B, B→C, A→C만 있다면 방향을 따라 출발점으로 돌아올 수 없다. 방향을 지워 그렸을 때 삼각형처럼 보여도 유향 순환이 없는 DAG일 수 있다. 무향 순환과 유향 순환을 구별한다.
선후 조건
작업 A가 B보다 먼저 끝나야 한다는 조건을 A→B로 나타낼 수 있다. A→B→C→A 같은 순환은 각 작업이 다른 작업을 먼저 요구하게 만들어 일관된 선후 나열을 막는다.
위상 정렬
유한 DAG의 정점은 모든 간선의 출발점이 도착점보다 앞에 오도록 나열할 수 있다. 이를 위상 정렬이라고 한다. 서로 선후 조건이 없는 정점의 순서는 달라질 수 있다.
트리와의 차이
DAG는 하나의 루트나 모든 정점의 연결을 요구하지 않는다. 한 정점으로 여러 경로가 모일 수도 있다. 순환이 없다는 공통점만으로 모든 DAG를 트리라고 부르지는 않는다.
관련 문서
유향 그래프 / 위상 정렬 / 트리 (그래프 이론) / 관계의 합성 / 정점 (그래프 이론) / 간선 (그래프 이론)