DAG数学基础
定义：在有向图G=(V,E)中，对于任意一个顶点v∈V，都不存在一条路径p=(e1,e2,…),ei∈E，使得从v开始出发到v终止，则G称为有向无环图（DAG, Directed Acyclic Graph）
在图论中，相比于一般图，DAG的很多问题可以在多项式级甚至线性复杂度条件下得到求解。DAG具有以下几条数学性质：
l DAG具有拓扑顺序，即DAG的所有节点可以转换为节点序列（线性化），使得每条边的起始节点位于终止节点之前，且该过程可以在线性复杂度条件下完成；
l DAG中相互连通的节点可以进行排序，如果从节点u出发可 ...
阅读全文
