DAG

수학적 정의에서 방향성 비순환 그래프(DAG)는 그래프 이론의 기본적인 객체인 방향 그래프(Directed Graph)의 특수한 형태이다. 이는 정점(vertex 또는 node)의 집합 V와 방향이 있는 간선(edge 또는 arc)의 집합 E로 구성되며, E의 각 원소는 순서쌍 (u, v)로 표현되어 정점 u에서 정점 v로의 방향성을 가진다. DAG의 결정적인 조건은 이 그래프가 어떠한 순환(cycle)도 포함하지 않는다는 것이다. 즉, 어떤 정점 v에서 시작하여 방향성을 따라 간선들을 통해 이동할 때, 출발점 v로 다시 돌아올 수 있는 경로가 존재하지 않는다.

이러한 비순환성은 DAG를 일반적인 방향 그래프와 구분짓는 핵심 속성이다. 순환이 없다는 것은 그래프 내에서 모든 연결 관계가 일정한 방향성을 유지하며, 정점들 사이에 부분 순서 관계(partial order)를 자연스럽게 정의할 수 있게 한다. 이 부분 순서는 한 작업이 다른 작업보다 반드시 먼저 완료되어야 한다는 선후 관계를 모델링하는 데 적합하다. 따라서 DAG는 작업 간의 의존성을 표현하는 수학적 모델로서 널리 사용된다.

DAG의 구조는 트리(Tree)와 유사점을 가지지만, 트리는 각 노드가 최대 하나의 부모 노드를 가지는 계층적 구조인 반면, DAG에서는 하나의 자식 노드가 여러 부모 노드로부터 의존성을 가질 수 있다는 점에서 더 일반화된 형태이다. 이는 복잡한 의존 관계를 표현하는 데 필수적이며, 위상 정렬과 같은 알고리즘을 적용하여 이러한 의존 관계를 해결할 수 있는 기반을 제공한다.

DAG의 가장 핵심적인 특성은 사이클, 즉 순환 구조가 존재하지 않는다는 점이다. 이는 어떤 노드에서 출발하여 방향성을 따라 간선을 타고 이동할 때, 절대 출발점으로 되돌아올 수 없음을 의미한다. 이러한 비순환성은 그래프에 방향성을 부여하는 동시에 구조에 엄격한 순서를 강제하게 된다.

이러한 사이클의 부재는 DAG를 트리와 같은 다른 비순환 구조와 구분 짓는 동시에, 방향 그래프의 특수한 형태로 만든다. 모든 트리는 DAG이지만, 하나의 부모 노드만을 가지는 트리와 달리 DAG는 하나의 노드가 여러 부모를 가질 수 있어 더 일반화된 구조를 표현할 수 있다. 이 특성은 선행 조건이 명확한 작업들의 흐름을 모델링하는 데 매우 적합하다.

사이클이 없다는 것은 그래프에 내재된 의존 관계가 모순되지 않음을 보장한다. 예를 들어, 작업 A가 작업 B의 완료를 필요로 하고, 동시에 작업 B가 작업 A의 결과에 의존하는 상황은 사이클을 형성하여 DAG에서는 표현될 수 없다. 이로 인해 DAG는 작업 스케줄링이나 빌드 시스템에서 의존성 해결의 기초가 되며, 위상 정렬이라는 유용한 알고리즘을 적용 가능하게 한다.

이 비순환성은 또한 데이터 처리 파이프라인에서 데이터의 흐름이 무한 루프에 빠지지 않도록 보장하며, 분산 원장 기술에서 트랜잭션의 검증 순서를 구성하는 데 핵심적인 역할을 한다. 따라서 사이클의 부재는 DAG가 단순한 그래프를 넘어 신뢰할 수 있는 순서와 의존성을 관리하는 강력한 도구로 사용되게 하는 근본적인 속성이다.

DAG의 핵심 특성 중 하나는 모든 간선이 방향을 가진다는 점이다. 이는 그래프 이론에서 방향 그래프(Directed Graph)의 한 종류로 분류되게 하는 근본적인 속성이다. 각 간선은 출발 노드에서 도착 노드로의 단방향 연결을 나타내며, 이로 인해 노드 간의 관계가 비대칭적이다. 예를 들어, 작업 A가 작업 B에 선행되어야 한다는 의존 관계는 A에서 B로 향하는 방향성 간선으로 표현된다. 이러한 방향성은 트리 구조와도 유사하지만, 트리는 각 노드가 최대 하나의 부모 노드를 가지는 계층적 구조인 반면, DAG에서는 하나의 노드가 여러 부모 노드를 가질 수 있어 더 복잡한 관계를 모델링할 수 있다.

방향성의 존재는 그래프의 순회와 해석에 결정적인 영향을 미친다. 경로 탐색이나 의존성 분석 시 반드시 간선의 방향을 따라야 하며, 역방향으로의 이동은 허용되지 않는다. 이는 실제 시스템에서의 인과 관계나 작업의 전후 관계를 자연스럽게 반영한다. 예를 들어, 데이터 처리 파이프라인에서 원본 데이터를 변환하는 여러 단계는 방향성 간선으로 연결되어 데이터의 흐름 방향을 명확히 정의한다. 또한, 버전 관리 시스템인 Git은 커밋 히스토리를 DAG로 관리하며, 각 커밋이 이전 커밋을 가리키는 방향성 덕분에 프로젝트의 변경 이력을 추적할 수 있다.

방향성과 비순환성은 서로 긴밀하게 연관되어 DAG의 유용성을 결정한다. 만약 방향성만 있고 순환이 존재한다면, 시스템은 무한 루프에 빠지거나 의존성 충돌을 일으킬 수 있다. DAG는 방향성을 유지하면서도 이러한 순환을 배제함으로써, 위상 정렬을 통한 선형적 실행 순서 결정이나 최단 경로 탐색과 같은 알고리즘의 적용을 가능하게 한다. 따라서 방향성은 DAG가 복잡한 관계를 구조적으로 표현할 수 있게 하는 틀을 제공하며, 동시에 그 비순환성과 결합되어 컴퓨터 과학 및 분산 시스템 전반에 걸쳐 강력한 모델링 도구로 사용되는 기반이 된다.

인접 리스트는 그래프를 표현하는 방법 중 하나로, 각 노드에 대해 그 노드와 직접 연결된 다른 노드들의 목록을 저장하는 방식이다. DAG와 같은 방향 그래프에서는 각 노드의 목록에 해당 노드에서 출발하는 간선이 향하는 목적지 노드들만을 기록한다. 이 방식은 인접 행렬에 비해 실제 존재하는 연결 관계만을 저장하므로, 간선의 수가 적은 희소 그래프에서 메모리 사용이 효율적이라는 장점이 있다.

인접 리스트의 구현은 일반적으로 배열 또는 연결 리스트의 배열을 사용한다. 각 인덱스는 하나의 노드를 나타내며, 해당 인덱스에 연결된 동적 배열이나 연결 리스트를 통해 인접 노드들을 관리한다. DAG에서 위상 정렬이나 깊이 우선 탐색과 같은 알고리즘을 수행할 때, 특정 노드의 후속 노드들을 빠르게 순회할 수 있어 유용하다.

이러한 특성으로 인해 DAG가 적용되는 작업 스케줄링이나 데이터 처리 파이프라인과 같은 분야에서는 작업 간 의존 관계, 즉 간선의 수가 전체적으로 제한적인 경우가 많아, 인접 리스트가 널리 사용되는 표현 방법이다.

인접 행렬은 그래프의 구조를 2차원 배열로 표현하는 방법이다. DAG를 포함한 모든 방향 그래프에 적용할 수 있으며, 행과 열이 각각 노드를 나타낸다. 행렬의 각 셀은 두 노드 사이의 연결 관계를 저장하는데, 일반적으로 두 노드 사이에 간선이 존재하면 1, 존재하지 않으면 0의 값을 가진다. DAG의 경우 간선에 방향이 있으므로, 인접 행렬은 대칭적이지 않다. 즉, 노드 A에서 노드 B로 가는 간선이 있다면 행렬의 (A, B) 위치는 1이 되지만, (B, A) 위치는 0이 된다.

이 표현법의 주요 장점은 특정 두 노드 사이의 연결 존재 여부를 상수 시간(O(1))에 확인할 수 있다는 점이다. 또한 행렬 연산을 활용한 다양한 그래프 알고리즘을 적용하기에 용이하다. 그러나 노드의 수를 V라고 할 때, V^2 크기의 공간을 차지하므로, 간선의 수가 적은 희소 그래프에서는 메모리 사용 효율이 떨어진다. DAG는 일반적으로 특정 구조를 가지는 경우가 많아 상대적으로 간선이 적을 수 있어, 이 경우 인접 리스트가 더 효율적인 표현법이 될 수 있다.

인접 행렬은 DAG의 위상적 특성을 시각적으로 파악하는 데도 도움을 준다. 위상 정렬이 가능한 DAG의 인접 행렬은 적절한 노드 순서로 행과 열을 재배열했을 때, 주대각선 위쪽 영역(상삼각행렬)에만 값이 존재하도록 만들 수 있다. 이는 모든 간선이 뒤쪽 노드에서 앞쪽 노드를 가리키지 않음을 의미하며, 그래프에 사이클이 없음을 보여주는 간접적인 증거가 된다.

위상 정렬 표현은 방향성 비순환 그래프의 고유한 특성을 활용하여 노드들을 선형 순서로 나열하는 방법을 의미한다. 이 표현은 그래프의 모든 간선이 왼쪽에서 오른쪽 방향을 가리키도록, 즉 모든 선행 관계가 만족되도록 노드들을 일렬로 배치하는 것을 목표로 한다. 이러한 표현은 작업 스케줄링이나 의존성 관리와 같은 문제에서 선행 조건이 충족된 순서를 명확하게 보여주는 데 유용하다.

위상 정렬 표현을 생성하는 대표적인 알고리즘으로는 칸 알고리즘과 DFS 기반 위상 정렬이 있다. 칸 알고리즘은 진입 차수가 0인 노드들을 큐에 반복적으로 추가하고 제거하는 과정을 통해 순서를 구축하는 반면, DFS 기반 위상 정렬은 깊이 우선 탐색의 종료 순서를 역으로 이용한다. 두 알고리즘 모두 결과적으로 동일한 위상 순서를 도출할 수 있으며, 그래프에 사이클이 존재할 경우 유효한 순서를 찾을 수 없다는 점에서 DAG의 검증 도구로도 사용된다.

이 표현은 단순한 순서 나열을 넘어, 인접 리스트나 인접 행렬과 같은 기존 그래프 표현법에 동적인 순서 정보를 부여한다. 예를 들어, 빌드 시스템이나 패키지 관리자는 이 표현을 바탕으로 의존성이 해결된 최적의 작업 실행 순서를 결정한다. 또한, 데이터 처리 파이프라인에서 각 처리 단계의 실행 흐름을 설계할 때도 이 표현이 핵심적인 역할을 한다.

위상 정렬은 방향성 비순환 그래프(DAG)의 모든 노드를 방향성을 거스르지 않는 순서, 즉 선행 관계에 따라 일렬로 나열하는 알고리즘이다. 이는 그래프의 각 간선이 A에서 B로 향할 때, 정렬된 목록에서 A가 반드시 B보다 앞서 나와야 함을 의미한다. 작업 간의 의존성을 가진 작업 스케줄링이나 컴파일 시 소스 코드 파일의 처리 순서 결정 등 선후 관계가 중요한 문제를 해결하는 데 필수적이다.

위상 정렬을 수행하는 대표적인 알고리즘으로는 칸 알고리즘과 깊이 우선 탐색(DFS) 기반 방법이 있다. 칸 알고리즘은 각 노드로 들어오는 간선의 수(진입차수)를 계산하여, 진입차수가 0인 노드들부터 큐에 넣고 순서대로 제거해나가는 방식으로 동작한다. 노드를 제거할 때마다 해당 노드가 가리키는 다른 노드들의 진입차수를 감소시켜, 새롭게 진입차수가 0이 된 노드를 큐에 추가하는 과정을 반복한다. 이 방법은 직관적이며 그래프 순회를 효율적으로 수행할 수 있다.

반면, 깊이 우선 탐색을 이용한 방법은 그래프를 깊이 있게 탐색하며, 더 이상 방문할 후속 노드가 없는 노드부터 결과 스택에 담는 방식으로 진행한다. 탐색이 완료된 후 스택에서 노드를 꺼내면 위상 정렬된 순서를 얻을 수 있다. 두 알고리즘 모두 시간 복잡도는 노드 수(V)와 간선 수(E)에 대해 O(V+E)로 동일하지만, 칸 알고리즘은 의존성 구조 변화에 따라 동적으로 순서를 갱신해야 하는 경우나 사이클 감지가 주목적일 때 유용한 경우가 많다.

위상 정렬의 결과는 유일하지 않을 수 있으며, 하나의 DAG에서도 여러 개의 유효한 위상 순서가 존재할 수 있다. 이는 알고리즘의 초기 진입차수가 0인 노드들의 처리 순서나 깊이 우선 탐색의 시작 노드 선택에 따라 달라질 수 있기 때문이다. 또한, 그래프에 사이클이 존재할 경우 모든 노드를 방문하기 전에 더 이상 진입차수가 0인 노드가 남아있지 않게 되어 정렬을 완료할 수 없으며, 이는 해당 그래프가 DAG가 아님을 판별하는 데 활용될 수 있다.

DAG에서 최단 경로를 탐색하는 문제는 일반적인 그래프와 달리 사이클이 존재하지 않는다는 특성 덕분에 효율적으로 해결할 수 있다. 사이클이 없기 때문에 음의 가중치가 존재하더라도 벨만-포드 알고리즘이나 다익스트라 알고리즘과 같은 일반적인 최단 경로 알고리즘보다 더 간단한 접근이 가능하다.

가장 일반적인 방법은 위상 정렬을 먼저 수행한 후, 정렬된 순서대로 노드를 하나씩 방문하며 거리를 갱신하는 동적 계획법 기반의 알고리즘이다. 출발 노드의 거리를 0으로 설정하고, 위상 정렬된 순서에 따라 각 노드를 처리한다. 현재 노드에서 나가는 모든 간선을 검사하여 인접 노드의 예상 거리를 현재 노드의 거리와 간선의 가중치를 더한 값으로 업데이트한다. 이 과정은 모든 노드를 한 번씩만 처리하면 되므로, 시간 복잡도는 위상 정렬의 O(V+E)와 동일하다.

이 알고리즘은 DAG의 구조적 장점을 최대한 활용한다. 위상 정렬 순서는 모든 간선이 왼쪽에서 오른쪽으로 향하도록 노드를 나열한 것이므로, 어떤 노드를 처리할 때는 그 노드로 들어오는 모든 가능한 경로를 이미 고려한 상태가 된다. 따라서 각 노드에 대해 단 한 번의 연산으로 최단 거리를 확정할 수 있어 매우 효율적이다. 이 방법은 프로젝트 일정 관리에서 임계 경로를 찾는 CPM이나 작업 간 의존성이 있는 스케줄링 문제 등에 응용된다.

반면, DAG에서의 최장 경로 탐색은 최단 경로 알고리즘에서 거리 갱신 시 최솟값 대신 최댓값을 취하는 방식으로 동일한 원리로 풀 수 있다. 하지만 가중치에 -1을 곱해 최단 경로 문제로 변환하여 푸는 방법은 DAG가 아닌 일반 그래프에서는 사이클로 인해 적용하기 어렵지만, DAG에서는 사이클이 없어 가능한 경우도 있다.

방향성 비순환 그래프(DAG)에서 최장 경로를 탐색하는 문제는 최단 경로 문제와 대비되는 중요한 연산이다. 이는 특정 시작 노드에서 도착 노드까지 도달하는 여러 경로 중 간선의 가중치 합이 가장 큰 경로를 찾는 것을 의미한다. 일반적인 그래프에서는 사이클이 존재할 경우 최장 경로를 찾는 문제는 NP-난해 문제로 알려져 풀기 어렵지만, DAG는 사이클이 없기 때문에 다항 시간 내에 효율적으로 해결할 수 있다.

DAG에서 최장 경로 탐색은 주로 위상 정렬 순서를 기반으로 한 동적 계획법을 통해 수행된다. 알고리즘은 먼저 그래프의 모든 노드에 대해 위상 정렬을 수행하여 선후 관계에 따른 처리 순서를 얻는다. 그 후, 정렬된 순서대로 각 노드를 방문하며, 해당 노드로 들어오는 모든 인접 노드들로부터 계산된 경로값을 고려해 최장 경로 값을 갱신한다. 이 과정은 모든 노드가 처리될 때까지 반복되며, 각 노드까지의 최장 경로 길이와 그 경로를 구성하는 이전 노드 정보를 저장한다.

이 기법은 프로젝트 일정 관리에서 임계 경로를 분석하는 데 핵심적으로 적용된다. 예를 들어, 여러 작업과 그 사이의 의존 관계를 DAG로 모델링했을 때, 전체 프로젝트의 최소 완료 시간은 시작 작업부터 종료 작업까지의 최장 경로 길이와 동일하다. 이 최장 경로상에 있는 작업들은 지연이 전체 일정에 직접 영향을 미치는 임계 작업이 된다.

최장 경로 탐색 알고리즘의 시간 복잡도는 그래프 표현 방식에 따라 다르다. 인접 리스트를 사용하고 위상 정렬에 깊이 우선 탐색을 활용할 경우, 시간 복잡도는 O(V+E)로, 여기서 V는 정점의 수, E는 간선의 수를 나타낸다. 이는 DAG의 비순환적 구조 덕분에 가능한 효율적인 성능이다.

DAG는 작업 간의 선후 관계와 의존성을 명확하게 모델링하는 데 적합한 구조로, 작업 스케줄링 분야에서 널리 활용된다. 각 작업은 그래프의 노드로 표현되고, 작업 간의 의존 관계는 방향성을 가진 간선으로 표현된다. 예를 들어, 작업 B가 실행되기 위해서는 반드시 작업 A가 먼저 완료되어야 한다면, A에서 B로 향하는 간선이 생성된다. 이렇게 구성된 DAG를 통해 시스템은 작업들의 실행 순서를 명확히 파악하고, 병렬로 실행 가능한 작업들을 효율적으로 식별할 수 있다.

이러한 스케줄링은 빅데이터 처리 프레임워크인 아파치 스파크나 아파치 에어플로우의 핵심 작동 원리이다. 특히 복잡한 데이터 파이프라인을 구성할 때, 각 데이터 변환 또는 분석 단계를 노드로, 데이터의 흐름과 단계 간 의존성을 간선으로 표현하여 전체 작업 흐름을 DAG로 정의한다. 위상 정렬 알고리즘을 적용하면 이러한 의존 관계를 위반하지 않으면서 모든 작업을 실행할 수 있는 순서를 얻을 수 있으며, 서로 의존하지 않는 작업들은 동시에 실행되어 전체 처리 시간을 단축시킨다.

DAG 기반 스케줄링은 분산 컴퓨팅 환경과 클라우드 환경에서 자원 관리의 효율성을 극대화한다. 태스크 간 의존성이 시각적으로 명확하기 때문에, 특정 작업이 실패했을 때 해당 작업에 의존하는 후속 작업들만 중단하거나 재실행하는 정교한 오류 처리와 폴트 톨러런스 구현이 가능하다. 또한, 자원 할당을 최적화하기 위해 크리티컬 패스를 분석하는 데에도 유용하게 사용된다.

데이터 처리 파이프라인은 여러 단계의 데이터 변환 작업을 순차적으로 실행하는 시스템이다. DAG는 이러한 파이프라인의 작업 의존성과 실행 순서를 모델링하는 데 이상적인 구조를 제공한다. 각 작업은 그래프의 노드로 표현되고, 작업 간의 데이터 흐름은 방향성 간선으로 표현된다. 비순환 구조 덕분에 작업 간 순환 의존성이 발생하지 않아 파이프라인의 실행이 명확하게 정의될 수 있다.

파이프라인 설계에서 DAG는 각 작업 단계의 입력과 출력 의존성을 시각적으로 명시한다. 예를 들어, 데이터를 추출(Extract)한 후 변환(Transform), 적재(Load)하는 ETL 과정이나, 머신러닝 모델의 데이터 전처리, 학습, 평가 단계를 구성할 때 널리 사용된다. 아파치 에어플로우나 루이지와 같은 워크플로 관리 도구들은 DAG를 핵심 추상화 모델로 사용하여 복잡한 데이터 파이프라인의 오케스트레이션을 지원한다.

이 구조의 주요 장점은 작업의 병렬 실행을 최적화할 수 있다는 점이다. 위상 정렬을 통해 서로 의존하지 않는 독립적인 작업들을 식별하면, 이러한 작업들은 동시에 실행되어 전체 처리 시간을 단축시킬 수 있다. 또한, 특정 단계에서 작업이 실패하더라도 해당 노드와 그 후속 작업들만 재실행하면 되므로, 파이프라인의 견고성과 유지보수성을 높여준다.

의존성 관리는 소프트웨어 개발에서 라이브러리, 모듈, 패키지 간의 복잡한 관계를 구조화하고 해결하는 핵심 과정이다. DAG는 이러한 의존 관계를 모델링하는 데 이상적인 자료 구조로, 각 패키지를 노드로, 패키지 간의 의존 방향을 간선으로 표현한다. 이 구조는 시스템에 필요한 모든 구성 요소를 정확한 순서로 설치하거나 컴파일할 수 있도록 보장하며, 특히 APT나 Yum, npm, Maven과 같은 현대적인 패키지 관리자의 핵심 메커니즘으로 널리 사용된다.

의존성 그래프가 DAG가 되어야 하는 근본적인 이유는 순환 의존성의 부재에 있다. 만약 패키지 A가 B에, B가 C에, 그리고 C가 다시 A에 의존하는 순환이 발생하면, 어느 패키지를 먼저 설치해야 하는지 결정할 수 없는 모순적인 상황에 빠지게 된다. DAG는 이러한 순환을 구조적으로 허용하지 않으므로, 위상 정렬 알고리즘을 적용해 모든 의존성을 만족시키는 선형적인 설치 순서를 항상 도출할 수 있다.

이 모델은 빌드 자동화 도구인 Make나 Gradle에서도 광범위하게 응용된다. 소스 코드 파일, 목적 파일, 실행 파일 간의 컴파일 의존 관계를 DAG로 정의함으로써, 변경된 파일만을 정확히 식별하고 필요한 최소한의 작업만을 재수행하는 증분 빌드를 가능하게 한다. 결과적으로 DAG 기반 의존성 관리 시스템은 소프트웨어의 복잡성을 통제하고, 빌드의 정확성과 효율성을 크게 향상시키는 역할을 한다.

버전 관리 시스템에서 DAG는 파일의 변경 이력과 브랜치 간의 관계를 표현하는 핵심적인 데이터 구조로 활용된다. 기존의 중앙집중식 버전 관리 시스템이 선형적인 타임라인에 의존한 것과 달리, Git과 같은 현대적인 분산 버전 관리 시스템은 DAG를 사용하여 각 커밋을 노드로, 부모 커밋을 가리키는 관계를 방향성 간선으로 모델링한다. 이는 각 커밋이 하나 이상의 부모 커밋을 가질 수 있게 하여, 병렬적인 개발 흐름과 브랜치 병합의 역사를 자연스럽게 기록할 수 있게 해준다.

이 구조의 가장 큰 장점은 비순환적 특성 덕분에 모든 변경 이력이 명확한 선후 관계를 가진다는 점이다. 즉, 어떤 커밋에서 출발하더라도 그 조상 커밋들을 거슬러 올라갈 수는 있지만, 자식 커밋이나 형제 커밋을 통해 다시 출발점으로 돌아오는 순환 경로는 존재하지 않는다. 이는 프로젝트 히스토리의 무결성을 보장하며, 충돌 해결이나 특정 시점으로의 되돌리기와 같은 연산을 안정적으로 수행할 수 있는 기반을 제공한다.

DAG 기반 버전 관리 시스템에서는 위상 정렬의 원리가 내부적으로 적용되어 커밋 히스토리를 시간순이나 의존성 순서로 정렬하여 보여주는 것이 가능해진다. 또한, 두 브랜치의 최신 공통 조상 커밋을 찾는 3-way 병합과 같은 알고리즘도 DAG 구조 위에서 효율적으로 구현된다. 결과적으로 DAG는 버전 관리 시스템이 복잡한 소프트웨어 개발 협업 모델을 지원하고, 데이터의 무결성과 추적 가능성을 유지하는 데 필수적인 역할을 한다.

트리는 방향성 비순환 그래프의 특별한 형태이다. 모든 트리는 방향이 있고 순환이 없는 그래프 구조를 가지므로, DAG의 정의를 만족한다. 그러나 모든 DAG가 트리는 아니다. 트리는 임의의 두 노드 사이에 정확히 하나의 경로만 존재하며, 일반적으로 하나의 루트 노드를 가지고 모든 간선이 루트에서 멀어지는 방향을 가진다. 반면, 일반적인 DAG는 이러한 제약이 없어 노드 간에 여러 경로가 존재할 수 있고, 명시적인 루트 노드가 없을 수도 있다.

따라서 트리는 DAG의 엄격한 부분 집합으로 볼 수 있다. 이 관계는 데이터 구조나 파일 시스템의 디렉토리 계층을 모델링할 때 명확히 드러난다. 파일 시스템의 디렉토리 트리는 부모에서 자식으로 향하는 방향성을 가지며 순환이 발생하지 않으므로 DAG이다. 하지만 두 디렉토리가 하나의 공통 하위 디렉토리를 공유하는 등의 구조는 일반 DAG로는 표현 가능하지만, 트리 구조에서는 허용되지 않는다.

이러한 포함 관계 때문에 많은 그래프 알고리즘이 두 구조에 모두 적용될 수 있다. 예를 들어, 트리에서의 깊이 우선 탐색은 DAG에서도 유효하다. 그러나 DAG에만 적용되는 위상 정렬 같은 알고리즘은 트리에서도 실행 가능하지만, 트리의 계층적 특성 때문에 결과가 자명한 경우가 많다. 결국 트리는 방향성과 비순환성이라는 DAG의 핵심 속성을 공유하면서도 더 강한 제약 조건을 가진, 그래프 이론에서 중요한 기본 구조이다.

방향 그래프(Directed Graph)는 그래프 이론에서 노드와 간선으로 구성된 구조 중, 간선에 방향성이 부여된 그래프를 의미한다. 모든 간선이 한 방향으로만 연결되어 있어, 노드 A에서 노드 B로의 이동 가능성이 노드 B에서 노드 A로의 이동 가능성과 다를 수 있다는 점이 무방향 그래프와 구분되는 핵심 특징이다. 이러한 방향성은 의존성, 작업 순서, 정보 흐름 등 비대칭적 관계를 모델링하는 데 적합하다.

방향 그래프는 내부에 사이클(Cycle)이 존재할 수도 있고 존재하지 않을 수도 있다. 사이클이 하나라도 존재하는 경우 이를 일반적인 방향 그래프라고 하며, 어떤 노드에서 출발하여 간선의 방향을 따라 이동했을 때 자기 자신으로 돌아오는 경로가 전혀 없는 그래프를 특별히 방향성 비순환 그래프(DAG)라고 부른다. DAG는 순환 의존성이 없어 위상 정렬이 항상 가능하며, 작업 스케줄링이나 데이터 처리 파이프라인 설계에 널리 응용된다.

방향 그래프는 인접 행렬이나 인접 리스트 등 다양한 방식으로 표현되며, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 같은 기본적인 그래프 순회 알고리즘을 적용할 수 있다. 또한 방향성을 고려한 최단 경로 문제를 해결하는 다익스트라 알고리즘이나 벨만-포드 알고리즘 등에도 활용된다. 방향 그래프의 개념은 네트워크 이론, 데이터베이스의 참조 무결성, 소프트웨어 공학의 의존성 그래프 등 컴퓨터 과학의 여러 분야에서 기초가 된다.

위상 정렬을 수행하는 주요 알고리즘으로는 칸 알고리즘과 깊이 우선 탐색 기반 알고리즘이 있다. 두 알고리즘 모두 방향성 비순환 그래프에서만 적용 가능하며, 결과적으로 노드들의 선형 순서를 생성한다는 공통점을 가진다. 그러나 각 알고리즘은 동작 원리와 구현 방식, 그리고 특정 상황에서의 효율성에서 차이를 보인다.

칸 알고리즘은 진입 차수를 기반으로 하는 탐욕 알고리즘이다. 먼저 모든 노드의 진입 차수를 계산하고, 진입 차수가 0인 노드들을 큐에 넣는다. 큐에서 노드를 꺼내 정렬 결과에 추가한 후, 해당 노드에서 나가는 간선을 제거하여 인접 노드들의 진입 차수를 감소시킨다. 감소 결과 진입 차수가 0이 된 노드를 다시 큐에 추가하는 과정을 반복한다. 이 방법은 직관적이며, 다중 소스 위상 정렬이나 사이클 감지에 유용하다.

반면, 깊이 우선 탐색 기반 알고리즘은 재귀 또는 스택을 이용해 그래프를 탐색한다. 알고리즘은 아직 방문하지 않은 노드에서 깊이 우선 탐색을 시작하여, 더 이상 탐색할 자식 노드가 없을 때(즉, 후위 순회 시점에) 해당 노드를 결과 스택에 푸시한다. 모든 노드를 방문한 후 스택에서 노드를 꺼내면 위상 정렬된 순서가 얻어진다. 이 방법은 구현이 간결하고, 단일 소스에서의 정렬이나 특정 경로 탐색과 결합하기에 용이하다.

두 알고리즘의 시간 복잡도는 모두 O(V+E)로 동일하다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다. 선택은 주로 문제의 제약 조건과 필요에 따라 이루어진다. 예를 들어, 작업 간 의존 관계가 동적으로 변경되거나 진입 차수를 지속적으로 관리해야 하는 작업 스케줄링 시스템에서는 칸 알고리즘이 더 적합할 수 있다. 한편, 이미 그래프 구조가 고정되어 있고 재귀 구현이 편리한 경우에는 깊이 우선 탐색 기반 방법이 선호된다.