[[二元决策图]]是基于有向无环图的一种数据结构,用于表示[[布尔函数]]<ref>{{citation|first=C. Y.|last=Lee|title=Representation of switching circuits by binary-decision programs|journal=Bell System Technical Journal|volume=38|issue=4|pages=985–999|year=1959|doi=10.1002/j.1538-7305.1959.tb01585.x}}.</ref><ref>{{citation|first=Sheldon B.|last=Akers|doi=10.1109/TC.1978.1675141|title=Binary decision diagrams|journal=IEEE Transactions on Computers|volume=C-27|issue=6|pages=509–516|year=1978}}.</ref>。在二元决策图中,每个非汇节点对应一个布尔变量,每个汇和边则表示0或1。要找到一个[[解释 (逻辑)|解释]]的真值,只要从唯一的源顶点出发,沿着该顶点代表的布尔变量的实际真值所对应的出边一直前进,到达的汇则为其真值。如同有向无环词图可以被看作是trie的一种压缩形式一样,二元决策图可以被看作是[[决策树]]的压缩形式。它通过将导向相同结果的边重新汇合到一个顶点来节省空间。<ref>{{citation | [[二元决策图]]是基于有向无环图的一种数据结构,用于表示[[布尔函数]]<ref>{{citation|first=C. Y.|last=Lee|title=Representation of switching circuits by binary-decision programs|journal=Bell System Technical Journal|volume=38|issue=4|pages=985–999|year=1959|doi=10.1002/j.1538-7305.1959.tb01585.x}}.</ref><ref>{{citation|first=Sheldon B.|last=Akers|doi=10.1109/TC.1978.1675141|title=Binary decision diagrams|journal=IEEE Transactions on Computers|volume=C-27|issue=6|pages=509–516|year=1978}}.</ref>。在二元决策图中,每个非汇节点对应一个布尔变量,每个汇和边则表示0或1。要找到一个[[解释 (逻辑)|解释]]的真值,只要从唯一的源顶点出发,沿着该顶点代表的布尔变量的实际真值所对应的出边一直前进,到达的汇则为其真值。如同有向无环词图可以被看作是trie的一种压缩形式一样,二元决策图可以被看作是[[决策树]]的压缩形式。它通过将导向相同结果的边重新汇合到一个顶点来节省空间。<ref>{{citation |