# 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:

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

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

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

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.

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.