Can someone explain in simple terms to me what a directed acyclic graph is?

graph = structure consisting of nodes, that are connected to each other with edges

directed = the connections between the nodes (edges) have a direction: A -> B is not the same as B -> A

acyclic = "non-circular" = moving from node to node by following the edges, you will never encounter the same node for the second time.

A good example of a directed acyclic graph is a tree. Note, however, that not all directed acyclic graphs are trees.

Example uses of a directed acyclic graph in programming include more or less anything that represents connectivity and causality.

For example, suppose you have a computation pipeline that is configurable at runtime. As one example of this, suppose computations A,B,C,D,E,F, and G depend on each other: A depends on C, C depends on E and F, B depends on D and E, and D depends on F. This can be represented as a DAG. Once you have the DAG in memory, you can write algorithms to:

• make sure the computations are evaluated in the correct order (topological sort)
• if computations can be done in parallel but each computation has a maximum execution time, you can calculate the maximum execution time of the entire set

among many other things.

Outside the realm of application programming, any decent automated build tool (make, ant, scons, etc.) will use DAGs to ensure proper build order of the components of a program.

Several answers have given examples of the use of graphs (e.g. network modeling) and you've asked "what does this have to do with programming?".

The answer to that sub-question is that it doesn't have much of anything to do with programming. It has to do with problem solving.

Just like linked-lists are data structures used for certain classes of problems, graphs are useful for representing certain relationships. Linked lists, trees, graphs, and other abstract structures only have a connection to programming in that you can implement them in code. They exist at a higher level of abstraction. It's not about programming, it's about applying data structures in the solution of problems.

Directed Acyclic Graphs (DAG) have the following properties which distinguish them from other graphs:

1. Their edges show direction.
2. They don't have cycles.

Well, I can think of one use right now - DAG (known as Wait-For-Graphs - more technical details) are handy in detecting deadlocks as they illustrate the dependencies amongst a set of processes and resources (both are nodes in the DAG). Deadlock would happen when a cycle is detected.

I assume you already know basic graph terminology; otherwise you should start from the article on graph theory.

Directed refers to the fact that the edges (connections) have directions. In the diagram, these directions are shown by the arrows. The opposite is an undirected graph, whose edges don't specify directions.

Acyclic means that, if you start from any arbitrary node X and walk through all possible edges, you cannot return to X without going back on an already-used edge.

Several applications:

• Spreadsheets; this is explained in the DAG article.
• Revision control: if you have a look at the diagram in that page, you will see that the evolution of revision-controlled code is directed (it goes "down", in this diagram) and acyclic (it never goes back "up").
• Family tree: it's directed (you are your parents' child, not the other way around) and acyclic (your ancestors can never be your descendant).

Graphs, of all sorts, are used in programming to model various different real-world relationships. For example, a social network is often represented by a graph (cyclic in this case). Likewise, network topologies, family trees, airline routes, ...

A directed acyclic graph is useful when you want to represent...a directed acyclic graph! The canonical example is a family tree or genealogy.