在一个有向图中，我们称任一有向边ni→nj(或表示为有序对（ni，nj）)中的结点ni为结点nj的前驱（父结），结点nj为结点ni的后继（子结）。又称任一有向边序列n1→n2，n2→n3，…，nk-1→nk为从结点n1到结点nk的一条通路。如果其中n1＝nk，则称该通路为环路。该结点序列也记为（n1，n2，…，nk）。例如，图11.7中有向图的通路（n2，n2）和（n3，n4，n3）就是环路。如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称DAG。图11.8的有向图就是一个DAG。在DAG中，如果（n1，n2，…，nk）是其中一条通路，则称结点n1为结点nk的祖先，结点nk为结点n1的后代。图11.8中结点n6就是结点n9的祖先，n9是n6的后代。
图 11.7有向图
图 11.8DAG
　　我们要用到的有向图，是一种其结点带有下述标记或附加信息的DAG：
　　① 图的叶结点，即无后继的结点，以一标识符（变量名）或常数作为标记，表示这个结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为这个结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。
　　② 图的内部结点，即有后继的结点,以一运算符作为标记，表示这个结点代表应用该运算符对其后继结点所代表的值进行运算的结果。
　　③ 图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。