更新时间：2023-06-25 23:52
dag图，信息技术术语，DAG数据结构跟踪基本块中值和变量的计算和赋值 ；块中使用的来自别处的值表示为叶子结点 ；值上的操作表示为内部结点 ；新值的赋值表示为将目标变量或临时变量的名字附加到表示赋值的结点上。
术语简介
DAG图：无回路有向图(Directed Acyclic Graph)
DAG 上的问题
SPOJ 4882 Counting in a DAG
编译原理中的DAG：
基本块的有向无环图（DGA）：
拓展：基本块划分，主要依据流图构造，就是按照if，while等跳转时需要的lab位置划分。例如：
label L2t2=fact*xfact=t2t3=x-1x=t3t4=x==0if_false t4 goto L2
其DAG为：
在数学和计算机科学的，有向无环图（DAG，/ˈdaelig; ɡ/), is a directed graphwith no directed cycles. 是一个有向图，无定向的周期。That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again. [ 1 ][ 2 ][ 3 ]也就是说，它是由集合的顶点和有向边构成，每条边连接一个顶点到另一个，这样，在一些顶点v开始，沿着有序的边，最终循环回再次到V是不可能的。[ 1][2][3]
DAGs may be used to model several different kinds of structure in mathematics and computer science.的DAG可用于对数学和计算机科学中得一些不同种类的结构进行建模。A collection of tasks that must be ordered into a sequence, subject to constraints that certain tasks must be performed earlier than others, may be represented as a DAG with a vertex for each task and an edge for each constraint; algorithms for topological orderingmay be used to generate a valid sequence，由于受制于某些任务必须比另一些任务较早执行的限制，必须排序为一个队列的任务集合可以由一个DAG图来呈现，其中每个顶点表示一个任务，每条边表示一种限制约束，拓扑排序算法可以用来生成一个有效的序列。DAGs may also be used to model processes in which information flows in a consistent direction through a network of processors.DAG也可以用来模拟信息沿着一个一致性的方向通过处理器网络的过程。The reachabilityrelation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability.DAG中得可达性关系构成了一个局部顺序，任何有限的局部顺序可以由DAG使用可达性来呈现，Additionally, DAGs may be used as a space-efficient representation of a collection of sequences with overlapping subsequences.此外，DAG的可作为一个序列集合的高效利用空间的重叠的子序列的代表性。
The corresponding concept for undirected graphsis a forest, an undirected graph without cycles.相对应的概念，无向图是一个森林，无环的无向图。 Choosing an orientation for a forest produces a special kind of directed acyclic graph called a polytree.选择森林的一个方向，产生了一种特殊的有向无环图称为polytree 。 However there are many other kinds of directed acyclic graph that are not formed by orienting the edges of an undirected acyclic graph.不过，也有其他种类的向无环图，它们不是由面向无向无环图的边构成的。For this reason it may be more accurate to call directed acyclic graphs acyclic directed graphs or acyclic digraphs .出于这个原因，称其为有向无环图比无环有向图或者无环图更确切。