자료구조 - 비순환 방향 그래프 (DAG, Directed Acyclic Graph)

1. 비순환 방향 그래프란?

비순환 방향 그래프(DAG, Directed Acyclic Graph)란 순환을 가지지 않는 방향그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다.

 

1) 선행자(predecessor), 후행자(successor)

DAG에서 어떤 정점 vi, vj에 대해서 vi에서 vj로의 경로가 존재하면, vi, vj의 선행자(predecessor), vj는 vi의 후행자(successor)라고 한다.

 

2) 즉각 선행자(immediate predecessor), 즉각 후행자(immediate successor)

DAG에서 어떤 정점 vi, vj에 대해서 vi에서 vj로의 간선이 존재하면, vi를 vj의 즉각 선행자(immediate predecessor), vj를 vi의 즉각 후행자(immediate successor)라고 한다.