DAG
비순환 방향 그래프; Directed Acyclic Graph
순환을 포함하지 않은 방향 그래프
\( e = (u, v) \)라면, \( e \)를 \( u \)에서 \( v \)로 가는 변이라고 한다.
꼭짓점 \( v \)는 변 \( e \)의 머리라고 하며, 꼭지점 \( u \)는 변 \( e \)의 꼬리라고 한다.
위상 정렬
Topological Sorting
변 (u, v)들에 대해 u가 v 전에 선행하도록 나열한 꼭짓점의 선행 정렬
즉, 그래프의 방향성을 거스르지 않고 꼭짓점을 나열한 것이다.
아래 그림과 같이 나열한 것은 위상 정렬에 해당하지 않다.
하나의 방향 그래프는 여러 개의 위상 정렬을 가질 수 있다. 꼭짓점의 순서는 왼쪽에서 오른쪽 방향으로 진행한다. 정렬 과정은 아래 그림과 같다.
위상 정렬이 성립하기 위해서는 그래프의 순환이 존재하지 않아야 한다. 즉, DAG여야 한다.
예시
대표적으로 Git Branch 구조가 DAG에 해당한다.
또한, DAG는 작업의 우선순위, 스케쥴링을 표현할 때 사용한다.
참고 문서
https://bossm0n5t3r.github.io/posts/71/
https://velog.io/@kji990607/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DAG-Directed-Acyclic-Graph
https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC