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

[[파일:방향 비순환 그래프.png|섬네일|방향 비순환 그래프]]
'''방향 비순환 그래프'''(Directed Acyclic Graph, DAG)는 방향성을 가지며 순환이 없는 그래프를 의미한다. 즉, DAG에서는 어떤 노드에서 출발하여 방향을 따라가면 다시 원래 노드로 돌아올 수 있는 경로(순환, cycle)가 존재하지 않는다. DAG는 위상 정렬, 작업 스케줄링, 의존성 분석, 컴파일러 최적화, 블록체인 등의 다양한 응용 분야에서 활용된다.
==특징==
*'''방향성'''을 가지며, 각 간선은 특정한 방향을 따른다.
*'''순환이 존재하지 않음''' → 어떤 노드에서 시작하여 방향을 따라 이동했을 때 다시 원래 노드로 돌아올 수 없다.
*모든 DAG는 최소 하나 이상의 '''위상 정렬'''을 가질 수 있다.
*DAG에서 모든 노드의 진입 차수가 0이 되도록 간선을 제거하면 '''유향 비순환 연결 요소'''(Strongly Connected Component, SCC)를 찾을 수 있다.
==예제==
다음 그래프는 DAG의 예시이다.
  5 → 0 → 2  
  5 → 1 → 2  
  4 → 1  
  4 → 3 → 2  
  3 → 1  
이 그래프는 방향성을 가지며, 어떤 노드에서 출발하여 방향을 따라 이동해도 다시 원래 위치로 돌아오는 순환이 존재하지 않는다.
==DAG 판별 알고리즘==
DAG인지 확인하는 방법은 다음과 같다.
===1. [[위상 정렬]]을 이용한 방법===
*위상 정렬을 수행하여 모든 노드를 방문하면 DAG이다.
*위상 정렬 도중 더 이상 방문할 수 없는 노드가 남아 있다면 순환이 존재하는 그래프이다.
===2. DFS를 이용한 방법===
*DFS를 수행하면서 '''방문 중''' 상태의 노드를 다시 방문하면 순환이 존재하는 것이다.
==코드 예제==
<syntaxhighlight lang="python">
from collections import deque

def is_dag(graph, n):
    in_degree = {i: 0 for i in range(n)}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in in_degree if in_degree[node] == 0])
    count = 0

    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return count == n  # 모든 노드를 방문했으면 DAG

# 예제 그래프 (DAG)
graph = {
    5: [0, 1],
    4: [1, 3],
    3: [1, 2],
    0: [2],
    1: [2],
    2: []
}

# DAG 판별 실행
print(is_dag(graph, 6))
</syntaxhighlight>
 출력 결과 예시:
 True
이 그래프는 DAG이므로 True가 출력된다.
==응용==
DAG는 다양한 분야에서 활용된다.
*'''위상 정렬''' → 작업 스케줄링, 강의 선수 과목 분석 등에 사용
*'''최단 경로 탐색''' → DAG에서는 벨만-포드나 다익스트라 알고리즘보다 더 빠르게 최단 경로를 찾을 수 있다.
*'''컴파일러 최적화''' → 코드 의존성을 DAG로 표현하여 최적화 가능
*'''블록체인''' → 일부 블록체인 구조(예: IOTA의 Tangle)는 DAG를 기반으로 구현됨
==같이 보기==
*[[위상 정렬]]
*[[강한 연결 요소]]
*[[그래프 이론]]
==참고 문헌==
*Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
[[분류:알고리즘]]
[[분류:그래프 이론]]