알고리즘/그래프
[CS] DAG와 위상정렬
DAG (Directed Acyclic Graph) DAG는 순환을 가지지 않는 방향 그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG 구조를 가진다. DAG에서 어떤 정점 \(v_i \in V, v_j \in V\) 에 대해서 \(v_i\) 에서 \(v_j\) 로의 경로가 존재하면, \(v_i\) 는 \(v_j\) 의 선행자이고 \(v_j\) 는 \(v_i\) 의 후행자이다. DAG에서 어떤 정점 \(v_i \in V, v_j \in V\) 에 대해서 \(v_i\) 에서 \(v_j\) 로의 간선이 존재하면, \(v_i\) 는 \(v_j\) 의 즉각 선행자이고 \(v_j\) 는 \(v_i\) 의 즉각 후행자이다. 위상정렬 DAG에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것을..
