방향 비순환 그래프

방향 비순환 그래프

방향 비순환 그래프(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를 수행하면서 방문 중 상태의 노드를 다시 방문하면 순환이 존재하는 것이다.

코드 예제

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))

출력 결과 예시:
True

이 그래프는 DAG이므로 True가 출력된다.

응용

DAG는 다양한 분야에서 활용된다.

• 위상 정렬 → 작업 스케줄링, 강의 선수 과목 분석 등에 사용
• 최단 경로 탐색 → DAG에서는 벨만-포드나 다익스트라 알고리즘보다 더 빠르게 최단 경로를 찾을 수 있다.
• 컴파일러 최적화 → 코드 의존성을 DAG로 표현하여 최적화 가능
• 블록체인 → 일부 블록체인 구조(예: IOTA의 Tangle)는 DAG를 기반으로 구현됨

같이 보기

• 위상 정렬
• 강한 연결 요소
• 그래프 이론

참고 문헌

• Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.