유향 비순환 그래프

유향 비순환 그래프(Directed Acyclic Graph, DAG)는 방향성을 가진 간선(Edges)을 포함하며, 순환(Cycle)이 존재하지 않는 그래프이다. DAG는 여러 알고리즘 및 데이터 구조에서 중요한 역할을 하며, 위상 정렬(Topological Sorting), 작업 스케줄링, 의존성 해결 등에 활용된다.

1 정의

유향 비순환 그래프(DAG)는 다음 조건을 만족하는 그래프이다.

• 유향 그래프 (Directed Graph)
  • 모든 간선이 특정 방향을 가지며, 한 정점에서 다른 정점으로 이동하는 방향이 정해져 있다.

• 비순환 (Acyclic)
  • 그래프 내에서 시작 정점으로 돌아오는 경로(순환 경로, Cycle)가 존재하지 않는다.
  • 즉, 정점 u에서 시작하여 u로 다시 돌아오는 경로가 없다.

DAG는 수학적으로 **(V, E)** 형태의 그래프로 표현되며, 여기서

• V : 정점(Vertex)들의 집합
• E : 방향성을 가진 간선(Edge)의 집합

2 예제

다음은 유향 비순환 그래프의 예제이다.

    A → B → D
    ↓    ↓
    C → E

위 그래프는 방향성을 가지면서도 순환이 없으므로 DAG에 해당한다.

3 특징

유향 비순환 그래프(DAG)는 다음과 같은 특징을 가진다.

• 위상 정렬(Topological Sorting)이 가능하다.
  • DAG에서는 모든 정점에 대해 위상 정렬이 가능하며, 특정 순서대로 정렬할 수 있다.

• 모든 DAG는 하나 이상의 출발점(Source)과 도착점(Sink)을 가진다.
  • 출발점(Source) : 진입 차수(In-degree)가 0인 정점
  • 도착점(Sink) : 진출 차수(Out-degree)가 0인 정점

• DAG는 항상 방향성이 있는 트리 구조를 포함할 수 있다.
  • 특정한 경우, DAG는 루트가 없는 트리와 유사한 구조를 가지며, 부모-자식 관계를 나타낼 수 있다.

4 위상 정렬 (Topological Sorting)

DAG에서는 위상 정렬(Topological Sorting)이 가능하다. 위상 정렬이란 모든 정점들을 간선의 방향을 유지하면서 선형적으로 정렬하는 방법이다.

위상 정렬을 수행하는 두 가지 주요 알고리즘:

• 카한(Kahn)의 알고리즘
  • 진입 차수(In-degree)가 0인 정점을 먼저 선택하여 정렬하는 방식
  • 큐(Queue)를 이용하여 구현할 수 있다.

• DFS 기반 알고리즘
  • DFS(깊이 우선 탐색, Depth First Search)를 활용하여 정렬하는 방식
  • 재귀 호출을 사용하여 후위 순회(Postorder Traversal)로 정점을 스택에 저장한 후 역순으로 출력한다.

4.1 위상 정렬 예제

주어진 DAG:

    1 → 2 → 4
    ↓    ↓
    3 → 5

가능한 위상 정렬 결과:

• `1 → 3 → 2 → 5 → 4`
• `1 → 2 → 3 → 5 → 4`
• `1 → 2 → 4 → 3 → 5`

(위상 정렬은 DAG의 구조에 따라 여러 가지 결과가 존재할 수 있다.)

5 DAG의 응용

유향 비순환 그래프(DAG)는 다음과 같은 분야에서 널리 사용된다.

• 컴파일러 및 빌드 시스템
  • 소스 코드의 의존성 분석 (예: Makefile, CMake)

• 작업 스케줄링 및 프로젝트 관리
  • 작업 간 선후 관계가 존재하는 경우 (예: PERT 차트)

• 데이터 흐름 분석
  • 신경망(Neural Network) 및 데이터 흐름 모델에서 활용됨

• 버전 관리 시스템(Git)
  • Git의 브랜치 구조는 DAG로 표현되며, 병합(Merge) 및 리베이스(Rebase) 과정에서 DAG를 활용한다.

6 사이클 검출 (Cycle Detection)

DAG인지 여부를 확인하려면 그래프에서 **순환(Cycle)이 존재하는지 검사**해야 한다. 다음 두 가지 방법이 주로 사용된다.

• DFS 기반 검출
  • DFS 탐색 중 방문 중(Gray) 상태의 정점을 다시 방문하면 사이클이 존재함을 의미한다.

• 카한(Kahn) 알고리즘 기반 검출
  • 위상 정렬을 수행한 후, 모든 정점을 방문하지 못하면 사이클이 존재하는 것이다.

7 같이 보기

• 위상 정렬
• 유향 그래프
• 트리 구조
• 컴퓨터 과학에서의 그래프 이론

8 참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
• Wikipedia - Directed Acyclic Graph (DAG)
• GeeksforGeeks - Topological Sorting