사이클이 없는 방향 그래프 DAG - Directed Acyclic Graph

DAG는 Topological Sort, Strongly Connected Component 등을 정의할 때 자주 사용되는 자료구조로

사이클이 존재하지 않는 방향 그래프

를 의미한다

DAG

DAG를 이해하기 위해

Directed graph G가 cycle이 있다 ↔ G의 DFS Tree가 back edge를 가지고 있다

이러한 성질들은 서로 필요충분조건을 만족한다는 사실을 알 필요가 있다

1️⃣ ⬅ (G의 DFS Tree가 back edge를 가지고 있다면 G에는 cycle이 존재한다)

: 그래프 G에서 임의의 정점 u와 v에 대해 back edge(v,u)가 존재한다고 가정한다(위의 그림). 그러면 u ➡ ... ➡ v ➡ u로의 cycle이 존재한다
2️⃣ ➡ (Directed Graph G가 cycle이 있다면 G의 DFS tree가 back edge를 가지고 있다)

: v ➡ v₁ ➡ v₂ ➡ ... vk ➡ v로의 cycle이 존재한다고 가정한다. 만약 vi (1≤i≤k)가 이 cycle의 node들 중 처음으로 방문하는 node라 하면 나머지 vertex들은 vi에서 reachable 하므로 DFS tree에서 모두 vi의 descendant가 된다. 따라서 (vi-1, vi)는 back edge가 된다

따라서 DAG는 DFS Tree를 생성했을 때 Back Edge를 가지지 않는다
DAG의 Vertex들은 Topological Sort를 이용한 Linear ordering이 가능하다
https://2jinishappy.tistory.com/161?category=903864

그래프의 Vertex를 정렬하는 Topological Sort - Kahn's Algorithm

DAG에서는 Source와 Sink라는 특별한 두 정점이 존재한다
Source는 indegree가 0인 vertex, Sink는 outdegree가 0인 vertex를 의미한다

Source와 Sink는 위의 그림처럼 DAG의 아무 vertex에서 시작하여 DFS tree를 생성했을 때 post(v)가 가장 큰 node가 source, 가장 작은 node가 sink가 된다