What is a DAG?

A directed acyclic graph is one of the most important data structures we deal with in software engineering. You can’t understand Git without grasping the main concepts of this data structure. In the next four articles, we’re going to go in depth into this powerful data structure, and see why it sits at the heart of so many things.

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:

basic 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).

dag

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.

gradle dag

Think of a family tree.

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

Wow! You read the whole thing. People who make it this far sometimes want to receive emails when I post something new.

I also have an RSS feed.