Can a DAG be disconnected?

Yes; separate components can each be acyclic.

Can a node point to itself?

No. A self-loop is a directed cycle.

Can a recurring workflow use a DAG?

Yes. Repeating executions need not create a cycle within each run's dependency graph.

Does every directed graph have a topological ordering?

No. For finite directed graphs, such an ordering exists exactly when there is no directed cycle.

AI Glossary / Graphs and symbolic AI / Advanced

Directed acyclic graph

Definition

A directed acyclic graph, or DAG, is a graph whose edges have directions and which contains no directed cycle. Following arrows along a nonempty path can never return to its starting node. DAGs are widely used to represent dependencies, allowing prerequisites to be arranged before the items that depend on them.

What it means

Directed specifies how an edge is followed. Acyclic excludes a loop that can be completed while respecting every arrow. It can also have several starting nodes, disconnected components, or nodes with multiple parents.
The structure does not determine what an arrow means. In a workflow it might indicate that one task must finish before another starts; in another application it represents a different relationship. A DAG is not automatically a tree, a complete schedule, or evidence that one event causes another.

How it works

For a finite DAG, a topological ordering lists all nodes so that each edge's starting node appears before its ending node. More than one ordering can satisfy the same graph.
One way to construct an ordering is to repeatedly select a node with no remaining incoming edges, place it next, and remove its outgoing edges from the working representation. This is the idea behind Kahn's algorithm. If nodes remain but none can be selected, a directed cycle prevents completion.
For a task graph, an execution system can use dependencies to determine which tasks are eligible to start. Eligibility does not ensure immediate execution: workers, memory, permissions, and other resources may still be unavailable. A topological ordering answers an ordering question, while a scheduler also decides when and where eligible work runs.

Three practical examples

Data preparation: A reporting workflow extracts data, applies transformations, and combines results. Arrows identify required upstream outputs. If two transformations are independent after extraction, the dependency structure can permit them to run concurrently when resources allow.
Software construction: A build system tracks which outputs depend on source files or other generated outputs. The graph helps determine a valid processing order. Incorrectly omitted dependencies can still produce wrong results even when the recorded graph is acyclic.
Spreadsheet calculation: Cells depend on the values of other cells referenced in their formulas. An acyclic dependency structure admits an evaluation order. Intentional iterative calculations require additional semantics; simply drawing a DAG does not capture arbitrary circular formulas.

Think of it this way

Imagine a set of instructions saying which preparations must precede which later steps. Several steps can share a prerequisite, and one later step can require several earlier results. A DAG permits a consistent forward order without a chain of requirements that eventually demands its own completion first.

Worked example

Create four tasks with durations in minutes: A takes 2, B takes 5, C takes 3, and D takes 1. Dependencies are A to B, A to C, B to D, and C to D. Each arrow means that the source task must finish before the destination starts, and D requires both its predecessors.
The sequences A-B-C-D and A-C-B-D are both valid topological orderings. Neither sequence proves that B must precede C or C must precede B; the graph imposes no ordering between them.
Assume tasks begin as early as possible, two suitable workers are available for B and C, and there are no setup or communication delays. A runs from time 0 to 2. B then runs from 2 to 7, while C runs from 2 to 5. D waits for both and runs from 7 to 8. Completion time is 8 minutes.
With only one worker and no overlapping tasks, the same dependencies require 2 + 5 + 3 + 1 = 11 minutes. The DAG is unchanged, but the resource assumption changes the schedule. Under the two-worker assumptions, A-B-D is the critical chain of duration 8.
Ignoring arrow directions, A-B-D-C-A forms a closed loop. This does not violate the DAG condition because those edges cannot be followed around that loop in their given directions. However, adding D to A creates directed cycles, including A-B-D-A, and destroys the possibility of a topological ordering.

Illustrative case study

Fictional Cedar Reports models its preparation workflow as a DAG. A dashboard initially presents the number of graph layers as though it were the total completion time. Reviewers find that task durations differ substantially and several eligible tasks share one constrained processing resource.
The team keeps the dependency graph but adds duration and resource information to scheduling analysis. It also checks that combined outputs wait for all required inputs and that a new dependency does not create a cycle.
The revised workflow separates a valid dependency structure from a realistic completion estimate.

Common misconceptions and mistakes

“A DAG must be a tree.” A node may have several parents and several distinct paths leading to it.
“A DAG has exactly one starting node.” Multiple nodes can have no incoming edges.
“No cycles means the drawing cannot contain a geometric loop.” Only directed cycles are excluded.
“A topological order is unique.” Independent choices can produce several valid orders.
“Acyclic dependencies guarantee a successful run.” Tasks, inputs, or resources can still fail.

Business use

Use a DAG when dependency direction and the absence of circular prerequisites match the process. Define whether multiple incoming edges mean that all upstream tasks must finish, or whether the application uses another explicit rule. Avoid relying on the diagram alone to communicate execution semantics.
Maintain the graph when inputs and processes change. Combine it with task durations, resource limits, and failure handling when estimating delivery time. An acyclicity check can catch circular dependencies, but it cannot detect every missing or incorrectly stated requirement.

Check your understanding

Why can B and C start together in the example?

Answer: Both depend on A, but neither depends on the other.

Why does one worker require more time?

Answer: The tasks cannot overlap despite the dependency structure permitting overlap.

Which added edge creates a cycle?

Answer: D to A.

Related terms

Directed graph
Critical path
dependency
topological ordering
in-degree
workflow
parallel execution
circular dependency

Learn next

Draw a small task DAG and list two valid topological orderings. Assign durations and compare schedules under different resource limits, then add a backward dependency and trace any resulting directed cycle.

Directed cycle

Sources

NetworkX, Directed Acyclic Graphs and Topological Sort: https://networkx.org/nx-guides/content/algorithms/dag/index.html Databricks technical terminology glossary, DAG workflow context: https://docs.databricks.com/aws/en/resources/glossary

Previous: Direct voice input Next: Directed cycle