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

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.

I see lot of answers indicating the meaning of DAG (Directed Acyclic Graph) but no answers on its applications. Here is a very simple one -

Pre-requisite graph - During an engineering course every student faces a task of choosing subjects that follows requirements such as pre-requisites. Now its clear that you cannot take a class on Artificial Intelligence[B] without a pre requisite course on Algorithms[A]. Hence B depends on A or in better terms A has an edge directed to B. So in order to reach Node B you have to visit Node A. It will soon be clear that after adding all the subjects with its pre-requisites into a graph, it will turn out to be a Directed Acyclic Graph.

If there was a cycle then you would never complete a course :p

A software system in the university that allows students to register for courses can model subjects as nodes to be sure that the student has taken a pre-requisite course before registering for the current course.

My professor gave this analogy and it has best helped me understand DAG rather than using some complicated concept!

Another real time example -> Real Time example of how DAG's can be used in version system

dots with lines pointing to other dots

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.