유향 비순환 그래프 편집하기

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

*'''비순환 (Acyclic)'''
**그래프 내에서 시작 정점으로 돌아오는 경로(순환 경로, Cycle)가 존재하지 않는다.
**즉, 정점 u에서 시작하여 u로 다시 돌아오는 경로가 없다.
DAG는 수학적으로 **(V, E)** 형태의 그래프로 표현되며, 여기서
*'''V''' : 정점(Vertex)들의 집합
*'''E''' : 방향성을 가진 간선(Edge)의 집합
==예제==
다음은 유향 비순환 그래프의 예제이다.<pre>
    A → B → D
    ↓    ↓
    C → E
</pre>위 그래프는 방향성을 가지면서도 순환이 없으므로 DAG에 해당한다.
==특징==
유향 비순환 그래프(DAG)는 다음과 같은 특징을 가진다.
*'''위상 정렬(Topological Sorting)이 가능하다.'''
**DAG에서는 모든 정점에 대해 위상 정렬이 가능하며, 특정 순서대로 정렬할 수 있다.

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

*'''DAG는 항상 방향성이 있는 트리 구조를 포함할 수 있다.'''
**특정한 경우, DAG는 루트가 없는 트리와 유사한 구조를 가지며, 부모-자식 관계를 나타낼 수 있다.
==위상 정렬 (Topological Sorting)==
DAG에서는 위상 정렬(Topological Sorting)이 가능하다. 위상 정렬이란 모든 정점들을 간선의 방향을 유지하면서 선형적으로 정렬하는 방법이다.

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

*'''DFS 기반 알고리즘'''
**DFS(깊이 우선 탐색, Depth First Search)를 활용하여 정렬하는 방식
**재귀 호출을 사용하여 후위 순회(Postorder Traversal)로 정점을 스택에 저장한 후 역순으로 출력한다.
===위상 정렬 예제===
주어진 DAG:<pre>
    1 → 2 → 4
    ↓    ↓
    3 → 5
</pre>가능한 위상 정렬 결과:
*`1 → 3 → 2 → 5 → 4`
*`1 → 2 → 3 → 5 → 4`
*`1 → 2 → 4 → 3 → 5`
(위상 정렬은 DAG의 구조에 따라 여러 가지 결과가 존재할 수 있다.)
==DAG의 응용==
유향 비순환 그래프(DAG)는 다음과 같은 분야에서 널리 사용된다.
*'''컴파일러 및 빌드 시스템'''
**소스 코드의 의존성 분석 (예: Makefile, CMake)

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

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

*'''버전 관리 시스템(Git)'''
**Git의 브랜치 구조는 DAG로 표현되며, 병합(Merge) 및 리베이스(Rebase) 과정에서 DAG를 활용한다.
==사이클 검출 (Cycle Detection)==
DAG인지 여부를 확인하려면 그래프에서 **순환(Cycle)이 존재하는지 검사**해야 한다.  다음 두 가지 방법이 주로 사용된다.
*'''DFS 기반 검출'''
**DFS 탐색 중 방문 중(Gray) 상태의 정점을 다시 방문하면 사이클이 존재함을 의미한다.

*'''카한(Kahn) 알고리즘 기반 검출'''
**위상 정렬을 수행한 후, 모든 정점을 방문하지 못하면 사이클이 존재하는 것이다.
==같이 보기==
*[[위상 정렬]]
*[[유향 그래프]]
*[[트리 구조]]
*[[컴퓨터 과학에서의 그래프 이론]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms''. MIT Press.
*[https://en.wikipedia.org/wiki/Directed_acyclic_graph Wikipedia - Directed Acyclic Graph (DAG)]
*[https://www.geeksforgeeks.org/topological-sorting/ GeeksforGeeks - Topological Sorting]
[[분류:알고리즘]]