Directed Acyclic Graph (DAG)

비순환 그래프 ( Directed Acyclic Graph (DAG) )

• 방향성이 있는 그래프 중에서, 순환이 존재하지 않는 형태

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

  • 아래 이미지를 기준으로 A 는 F 의 선행자이며, F 는 A 의 후행자이다.

    • A → B → E → F

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

  • 아래 이미지를 기준으로, B 는 C 의 즉각 선행자이며, C 는 B 의 즉각 수행자이다.

    • B → C 바로 연결 됨