비순환 유향 그래프(DAG)란 무엇인가?
이번 글에서는 데이터 구조에서 중요한 개념인 비순환 유향 그래프(Acyclic Digraph)에 대해 알아보겠습니다. 비순환 유향 그래프는 이름 그대로 방향성 순환(directed cycle)을 하나도 포함하지 않는 유향 그래프를 의미합니다.
쉽게 말해, 그래프의 어떤 간선을 따라 이동하더라도 다시 시작점으로 되돌아오는 경로가 존재하지 않는 그래프입니다. 이러한 그래프는 영어로 Directed Acyclic Graph라고 하며, 줄여서 DAG라고 부릅니다.
DAG의 핵심 성질
모든 유한한(finite) DAG에는 반드시 출력 차수(out-degree)가 0인 노드가 최소 한 개 이상 존재합니다. 여기서 출력 차수란 해당 노드에서 나가는 간선의 개수를 뜻합니다.
만약 모든 노드의 출력 차수가 1 이상이라면, 간선을 계속 따라가다 결국 같은 노드를 다시 방문하게 됩니다. 이는 곧 순환이 존재한다는 의미이므로 DAG의 정의에 모순됩니다. 따라서 출력 차수가 0인 노드가 반드시 존재해야 하는 것입니다.
DAG 예제
노드의 개수에 따른 대표적인 DAG 예시는 다음과 같습니다.
노드가 1개인 DAG 예시 −
노드가 2개인 DAG 예시 −
노드가 3개인 DAG 예시 −
DAG의 주요 활용 분야
DAG는 순환이 없다는 특성 덕분에 작업 간의 선후 관계를 명확하게 표현할 수 있습니다. 이러한 이유로 위상 정렬(topological sort), 작업 스케줄링, 소프트웨어 빌드 시스템의 의존성 관리, 버전 관리 시스템(Git), 스프레드시트 수식 계산 등 다양한 컴퓨터 과학 분야에서 널리 활용되고 있습니다.