Menu
Can someone explain in simple terms to me what a directed acyclic graph is? I have looked on Wikipedia but it doesn't really make me see its use in programming.
964
The Directed Acyclic Graph (DAG) is used to represent the structure of basic blocks, to visualize the flow of values between basic blocks, and to provide optimization techniques in the basic block.
A directed acyclic graph (DAG) is a conceptual representation of a series of activities. The order of the activities is depicted by a graph, which is visually presented as a set of circles, each one representing an activity, some of which are connected by lines, which represent the flow from one activity to another.
It is used to implement transformations on basic blocks. DAG provides a good way to determine the common sub-expression. It gives a picture representation of how the value computed by the statement is used in subsequent statements.
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.
175
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
