Overview
A Directed Acyclic Graph, or DAG, has directed edges but no path that starts at a node and returns to it. DAGs model prerequisite and dependency structure.
FoundationSource checked
Directed Acyclic Graph
Represents directed dependencies with no cycle following edge directions.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Graph Structure
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
directed edgeacyclicitydependencytopological order
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V + E)
When to Use
- Use it when dependencies must have a valid before-after order.
- Use it when cycles should be rejected as invalid.
- Use it for dynamic programming over partial orders.
When Not to Use
- Avoid it when feedback loops or cyclic dependencies are meaningful.
- Avoid assuming a graph is a DAG without cycle detection.
- Avoid it when edge direction has not been defined.
What It Does
- Models one-way dependencies
- Supports ordering and dynamic programming over acyclic structure
Use Cases
- Build systems
- Task scheduling
- Dataflow and compiler dependency graphs
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Pseudocode
- 1.Prepare the inputs and state needed for Directed Acyclic Graph.
- 2.Apply the directed edge step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return stored structure.
Canonical Example
- Input
- compile -> test -> package
- Output
- a DAG with compile before test before package
- Explanation
- Following the arrows never returns to an earlier task.
Implementation Notes
- Run cycle detection or topological sorting to validate the DAG property.
- Document whether edges point from prerequisite to dependent or the reverse.
- Use topological order for many DAG algorithms.
Common Pitfalls
- Mistaking an undirected acyclic graph for a DAG.
- Ignoring cycles introduced by updates.
- Reversing prerequisite and dependent edge direction.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 4: Prepare the inputs and state needed for Directed Acyclic Graph.
data-structures-mechanismNotes
A DAG is a graph structure, not one specific traversal algorithm.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookReference for Directed Acyclic Graph DAG structure, topological ordering, and graph algorithm use.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byTopological Sort
Graph Traversal · Foundation
Topological sorting is defined over directed acyclic graphs.
Compare with thisUsed byDynamic Programming on DAGs
Graph Traversal · Core
DAG dynamic programming relies on acyclic dependency order.
Compare with thisRelationships
View full relationship pageUsed byDynamic Programming on DAGs
DAG dynamic programming relies on acyclic dependency order.
Used byTopological Sort
Topological sorting is defined over directed acyclic graphs.
Related Algorithms
Tags
Data StructureGraphDirected Acyclic GraphTopological Order