DAG
방향 비순환 그래프(DAG)는 노드 집합과 방향 간선 집합으로 구성된 그래프 구조의 한 유형으로, 각 간선은 한 노드에서 다른 노드로 향하는 방향을 가지며, 그래프에는 순환이 존재하지 않습니다(즉, 한 노드에서 시작하여 방향 간선을 따라가 다시 같은 노드로 돌아올 수 없습니다). 따라서 DAG는 순환이 없는 방향 그래프입니다.
DAG는 작업 스케줄링, 컴파일러 최적화, 의존성 분석 등 다양한 분야에서 폭넓게 활용됩니다. 이러한 응용에서 DAG는 일반적으로 작업 간의 의존성이나 계산 과정 내의 데이터 흐름을 표현하는 데 사용됩니다.
위상 정렬
위상 정렬은 그래프 이론과 프로젝트 관리에서 방향 비순환 그래프(DAG)의 노드(또는 작업)를 선형으로 정렬하는 데 사용되는 기본 알고리즘입니다. 위상 정렬의 목표는 모든 방향 간선 (u, v)에 대해 선형 순서에서 노드 u가 노드 v보다 앞에 오도록 노드를 배열하는 것입니다. 다시 말해, 의존성을 준수하면서 작업을 완료하거나 요소를 처리하기 위한 일관된 순서를 확립합니다.
위상 정렬의 핵심 사항:
-
방향 비순환 그래프(DAG): 위상 정렬은 순환이 없는 방향 그래프에만 적용할 수 있습니다. 순환은 작업 순서에 모호성을 초래하여 위상 순서를 불가능하게 만들기 때문입니다.
-
의존성 해결: 위상 정렬은 의존성이 있는 일련의 작업이나 활동이 있을 때 특히 유용합니다. 작업이 올바른 순서로 실행되도록 보장하여, 다른 작업에 의존하는 작업이 그 선행 조건이 완료되기 전에 시작되지 않도록 합니다.
-
응용:
- 프로젝트 관리: 위상 정렬은 프로젝트의 작업을 일정에 맞게 배치하여 프로젝트가 제때 완료되도록 돕습니다.
- 컴파일러 최적화: 컴파일러 설계에서 코드 생성이나 프로그램 세그먼트 최적화를 위한 최적의 순서를 결정하는 데 도움을 줍니다.
- 의존성 분석: 소프트웨어 공학에서 모듈, 함수, 클래스 간의 의존성을 분석하는 데 사용됩니다.
- 강의 일정 편성: 학술 기관에서 선수 과목을 기준으로 강의 일정을 편성하는 데 도움을 줍니다.
-
알고리즘: 여러 알고리즘이 위상 정렬을 수행할 수 있습니다. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 일반적으로 사용되는 접근 방식입니다. 알고리즘의 선택은 문제의 구체적인 요구 사항에 따라 달라집니다.
-
임계 경로: 위상 정렬은 프로젝트의 임계 경로, 즉 그래프를 통과하는 가장 긴 경로를 식별할 수도 있습니다. 임계 경로상의 작업은 지연될 경우 전체 프로젝트를 지연시키는 작업입니다.
-
다수의 유효한 순서: 주어진 DAG에는 여러 유효한 위상 순서가 존재할 수 있다는 점에 유의해야 합니다. 이러한 유연성은 최적화, 병렬 처리, 자원 할당을 가능하게 합니다.
전반적으로 위상 정렬은 방향 비순환 그래프가 널리 존재하는 다양한 응용 분야에서 의존성을 관리하고 작업이 올바른 순서로 실행되도록 보장하는 강력한 도구입니다.
DAG(Directed Acyclic Graph)에 대해 위상 정렬을 수행하는 데 일반적으로 사용되는 두 가지 알고리즘이 있습니다: DFS(Depth-First Search)와 BFS(Breadth-First Search)입니다. 두 알고리즘 모두 그래프의 노드에 대해 유효한 위상 순서를 찾는 데 사용할 수 있습니다. 각 알고리즘에 대한 설명은 다음과 같습니다:
-
DFS(Depth-First Search) 알고리즘:
- DAG의 임의의 노드에서 시작합니다.
- 그래프를 깊이 우선으로 순회하며 노드를 방문한 것으로 표시합니다.
- 방문하지 않은 이웃이 없는 노드(즉, 리프 노드)에 도달하면 해당 노드를 위상 순서의 맨 앞에 추가합니다.
- 모든 노드를 방문할 때까지 이 과정을 계속합니다.
DFS 기반 위상 정렬 알고리즘의 의사 코드:
function topologicalSort(graph): order = [] visited = set() for each node in graph: if node is not visited: visit(node, order, visited) return reverse(order) function visit(node, order, visited): mark node as visited for each neighbor of node: if neighbor is not visited: visit(neighbor, order, visited) append node to order -
Breadth-First Search (BFS) 알고리즘:
- 빈 큐와 위상 순서를 저장할 리스트를 초기화합니다.
- 진입 간선이 없는(진입 차수가 0인) 모든 노드를 큐에 넣는 것으로 시작합니다.
- 큐에 노드가 있는 동안 다음을 수행합니다.
- 노드를 큐에서 꺼내 위상 순서 리스트에 추가합니다.
- 각 인접 노드의 진입 차수를 1씩 감소시킵니다.
- 인접 노드의 진입 차수가 0이 되면 해당 노드를 큐에 넣습니다.
- 큐가 빌 때까지 위 과정을 반복합니다.
BFS 기반 위상 정렬 알고리즘의 의사 코드:
function topologicalSort(graph): order = [] queue = empty queue for each node in graph: if in-degree of node is 0: enqueue(node) while queue is not empty: node = dequeue(queue) append node to order for each neighbor of node: reduce in-degree of neighbor by 1 if in-degree of neighbor is 0: enqueue(neighbor) return order
DFS 기반과 BFS 기반 알고리즘 모두 DAG에 대해 유효한 위상 순서를 생성합니다. 둘 중 어느 것을 선택할지는 성능과 문제의 구체적인 요구 사항 등의 요인에 따라 달라집니다.