Software Engineering Blog

moon indicating dark mode
sun indicating light mode

What is a DAG?

May 06, 2019

A graph is a data structure, defined by its vertices and edges. Oftentimes you’ll see it defined as G = (V, E). That just means, “G is the graph defined by vertices V and edges E”.

We usually draw them like this:

Graph

We call a graph connected if there is a path from any vertex to any other vertex.

Connected Graph

A cycle in a graph is a path from a vertex back to itself, where each edge is only travelled once (the above graph does not contain a cycle).

Cyclic Graph

In a directed graph, each edge has a direction, meaning it goes from one vertex to another vertex. We draw directed graphs like this.

Directed Graph

Directed graphs can have cycles too, like the above one in red. When a directed graph doesn’t have a cycle, we call it a directed acyclic graph (a DAG). (The changed edge to remove the cycle is shown in gold).

Directed Acyclic Graph

In short, that is a directed acyclic graph. A graph that is directed and has no cycles.

And what is a tree?

A related but different concept is a tree. A tree (in graph theory) is a graph where there is exactly one path from any vertex to any other. Or, more formally, a connected, undirected, acyclic graph.

Directed Acyclic Graph

Think of a family tree.

We’ll dive deeper into the DAG in articles to come.