共计 6944 个字符，预计需要花费 18 分钟才能阅读完成。
何为有向无环图？
1、首先它是一个图，然后它是一个有向图，其次这个有向图的任意一个顶点出发都没有回到这个顶点的路径，是为有向无环图
2、DAG（Directed Acyclic Graph）不一定能转化为树，但是树一定是一个 DAG
DAG 相关问题
- 拓扑序列
图中任意一对顶点 u 和 v，若边 (u,v)∈E(G)，则 u 在线性序列中出现在 v 之前。拓扑排序主要用来解决有向图中的依赖问题
求一个 DAG 的一条拓扑序列：
1. 找到当前所有的无直接前驱的节点(入度为 0)，若没有这样的顶点，跳到 3。若有，从中选一个 v，标记为已访问，加入到当前序列的尾部，继续 2。
2. 将从 v 出发的有向边全部删除(这样会得到一个新的有向图 G’)。
3. 如果序列中的顶点数不等于有向图 G 的顶点个数，则说明图 G 中存在环；如果相等，则该序列即是所求的拓扑序列。
{1, 2, 4, 3, 5}
- 判断是否成环
1、执行拓扑排序，如果序列中的顶点数不等于有向图 G 的顶点个数，则说明图 G 中存在环。
2、深度优先遍历该图，如果在遍历的过程中，发现某个节点有一条边指向已经访问过的节点，并且这个已访问过的节点不是当前节点的父节点（这里的父节点表示 dfs 遍历顺序中的父节点），则表示存在环。
换种说法： 1 条深度遍历路线中如果有结点被第二次访问到，那么有环。
bool dfs(int i,int pre){visit[i]=true;
for(int j=1;j<=v;j++)
if(g[i][j])
{if(!visit[j])
return dfs(j,i);
else if(j!=pre) // 如果访问过，且不是其父节点，那么就构成环
return true;
}
}- DAG 图（有向无环图）的最小路径覆盖
图存储
- 邻接矩阵
图的邻接矩阵（Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
设图 G 有 n 个顶点，则邻接矩阵是一个 n * n 的方阵
无向图：
有向图：
- 邻接表
邻接表的核心思想就是针对每个顶点设置一个邻居表。
以上面的图为例，这是一个有向图，分别有顶点 a, b, c, d, e, f, g, h 共 8 个顶点。使用邻接表就是针对这 8 个顶点分别构建邻居表，从而构成一个 8 个邻居表组成的结构，这个结构就是我们这个图的表示结构或者叫存储结构。
const node = [a, b, c, d, e, f, g, h];
const edges = [{b, c, d, e, f}, // a 的邻居表
{c, e}, // b 的邻居表
{d}, // c 的邻居表
{e}, // d 的邻居表
{f}, // e 的邻居表
{c, g, h}, // f 的邻居表
{f, h}, // g 的邻居表
{f, g}] // h 的邻居表图布局
graphlib
graphlib 提供表示图的数据结构。它不做布局或渲染
darge
dagre 执行节点，布局节点位置，其中所有节点通过一个 graphlib 图表示的布局（x 和 y 定位）。它不会渲染。
dagre-d3
dagre-d3 使用 dagre 进行布局，并使用 d3 进行渲染。请注意，dagre-d3 默认包含 dagre 和 graphlib，如 dagreD3.dagre 和 dagreD3.graphlib。
元素：
graph，即图整体，我们可以对图配置一些全局参数。
node，即顶点，dagre 在计算时并不关心 node 实际的形状、样式，只要求提供维度信息。
edge，即边，edge 需要声明其两端的 node 以及本身方向。例如 A -> B 表示一条由 A 指向 B 的 edge。
rank，即层级，rank 是 DAG 布局中的核心逻辑单位，edge 两端的 node 一定属于不同的 rank，而同一 rank 中的 node 则会拥有同样的深度坐标（例如在纵向布局的 graph 中 y 坐标相同）。
label，即标签，label 不是 DAG 中的必要元素，但 dagre 为了适用更多的场景增加了对 edge label 的布局计算。
深入理解 rank：
A->B;
B->C;
+---+ +---+ +---+
| A |------>| B |------->| C |
+---+ +---+ +---+A B C 分别处于 3 个 rank
A->B;
A->C;
+---+
--> | B |
+---+--/ +---+
| A |
+---+--\ +---+
--> | C |
+---+A 处于 rank1，B C 都处于 A 的下一层级 rank2
A->B;
B->C;
A->C;
+---+
-->| B |---\
+---+---/ +---+ --->+---+
| A | | C |
+---+------------------->+---+在这个示例中，我们发现 edge 两端的 node 可以相差超过一个 rank。由于 edge 两端的 node 不可属于同样的 rank，所以我们不能让 B 和 C 属于同一个 rank，进而最优的绘制结果为 A 和 C 之间相隔两个 rank。
布局算法
DAG 可以用于模型化许多不同种类的信息，因此将一个 DAG 数据结构可视化的需求也变得非常普遍。并且由于大部分图的数据都非常复杂甚至动态变化，所以自动、可配置的 DAG 可视化布局算法显然比人为排版更为高效且可靠。
约束条件：
- 结点之间不能有重叠
- 连线之间尽量减少交差
- 结点之间是有基本的层次关系对齐的
主要分 4 个步骤：
1、消除图中的环。
2、寻找最优的等级（分层）分配。
3、在同一个等级内，设置顶点的顺序，使交叉数最小。
4、计算顶点的坐标。
dagre 布局步骤：
removeSelfEdges // 删除自环边
acyclic.run // 反向设置成环的边
rank // 计算最优的等级分配
order // 同层排序
insertSelfEdges // 插入自环边
position // 计算顶点的坐标
acyclic.undo // 恢复反向边设置寻找成环的边：
遍历所有的节点，递归遍历每个节点的出边，把一条路径上的所有节点按路径顺序入栈，当遍历到某个出边的目标点已经在这个路径上遍历过了，那么这条边就是成环的边，存下来，然后对所有成环边反向。
function dfsFAS(g) {var fas = [];
var stack = {};
var visited = {};
function dfs(v) {if (_.has(visited, v)) {return;}
visited[v] = true;
stack[v] = true;
_.forEach(g.outEdges(v), function(e) {if (_.has(stack, e.w)) {fas.push(e);
} else {dfs(e.w);
}
});
delete stack[v];
}
_.forEach(g.nodes(), dfs);
return fas;
}算法：network-simplex（网络单纯型）longest-path（最长路径）
ranker=network-simplex
A->B->C->E;
A->D->F;
A->G->H->I->J;
+---+ +---+ +---+
>| B |------->| C |------->| E |
-/ +---+ +---+ +---+
-/
+---+-/ +---+ +---+
| A |------>| D |------->| F |
+---+-\ +---+ +---+
-\
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+ranker=longest-path
A->B->C->E;
A->D->F;
A->G->H->I->J;
+---+ +---+ +---+
--->| B |------->| C |------->| E |
-----/ +---+ +---+ +---+
-----/
+---+---/ +---+ +---+
| A |-------------------------------->| D |------->| F |
+---+-\ +---+ +---+
-\
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+longestPath 算法就是快速初始化一个层级关系，求出来的是一条路径的尽头都对齐，定为 0，然后逆向路径计算，都为负值。
深度优先遍历
function longestPath(g) {var visited = {};
// 深度优先
function dfs(v) {var label = g.node(v);
if (_.has(visited, v)) {return label.rank;}
visited[v] = true;
// g.outEdges(v) v 点的出度，v 的 rank 就是他出度的点的层级减去出度的 minlen，如果 v 是指向多个点的，那么就取最小的那个层级
var rank = _.min(_.map(g.outEdges(v), function(e) {return dfs(e.w) - g.edge(e).minlen;
}));
if (rank === Number.POSITIVE_INFINITY || // return value of _.map([]) for Lodash 3
rank === undefined || // return value of _.map([]) for Lodash 4
rank === null) {// return value of _.map([null])
rank = 0;
}
return (label.rank = rank);
}
_.forEach(g.sources(), dfs);
}
紧凑树型：
1、任意节点的层级必须满足边的长度大于等于边的 minlen 最小长度。
2、某条边的松弛度被定义为其长度和最小长度之间的差值，边的松弛度为 0，则为紧凑的。
从图中任意找一个节点，作为起点，从这个点开始递归找到一棵最大的紧凑树，并返回这颗树的节点个数。
递归遍历松弛度为 0 的节点加到新的树上，新树的节点个数少于旧树的节点个数，说明还有节点因为松弛度大于 0 而没被加到新树上。在所有的边里找只有起点或者终点只有一个在新树上的边，然后判断边的两个端点里不在新树上的节点是起点还是终点，如果是起点，则把新树上所有的点对应的旧树上的点的 rank 加这个点的松弛度，如果是终点则是减去松弛度。
function tightTree(t, g) {function dfs(v) {
// 遍历 v 节点的所有边，然后检查边的对点是否存在树上，不存在且该边是紧凑的即紧凑度是 0，则该点可以加到这棵树上
_.forEach(g.nodeEdges(v), function(e) {
var edgeV = e.v,
w = (v === edgeV) ? e.w : edgeV;
if (!t.hasNode(w) && !slack(g, e)) {t.setNode(w, {});
t.setEdge(v, w, {});
dfs(w);
}
});
}
_.forEach(t.nodes(), dfs);
return t.nodeCount();} +---+ +---+ +---+
--->| B |------->| C |------->| E |
-----/ +---+ +---+ +---+
-----/ -2 -1 0
+---+---/ +---+ +---+
| A |-------------------------------->| D |------->| F |
+---+-\ +---+ +---+
-4 -\ -1 0
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+
-3 -2 -1 0 +---+ +---+ +---+
>| B |------->| C |------->| E |
-/ +---+ +---+ +---+
-/ -2 -1 0
+---+-/ +---+ +---+
| A |-------------------------------->| D |------->| F |
+---+-\ +---+ +---+
-3 -\ -1 0
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+
-2 -1 0 1 +---+ +---+ +---+
>| B |------->| C |------->| E |
-/ +---+ +---+ +---+
-/ -1 0 1
+---+-/ +---+ +---+
| A |------>| D |------->| F |
+---+-\ +---+ +---+
-2 -\ -1 0
-\ +---+ +---+ +---+ +---+
>| G |------->| H |------->| I |------->| J |
+---+ +---+ +---+ +---+
-1 0 1 2排序：
每层中的顶点顺序决定了布局的边交叉情况，因此一个好的层级内顶点顺序应该要尽量少产生交叉边。
前提条件：分配完层级之后，跨越多个层级的边会被替换成由多条连接临时节点或者“虚拟节点”的单位长度的边。虚拟节点被安插到中间层级上，使得整张图中所有边都只连接相邻层级的节点。
理论：
把多层的 DAG 图，分成一个个的双层图，两层两层的进行排序。当访问某一层时，这一层每个顶点都会根据其关联的上一层顶点的位置分配一个权重。然后这一层的顶点会根据这个权重进行排序。
权重计算：定义一个两层图，下层节点根据上层节点排序，下层每个顶点 v 的权重等于：
每条与 v 关联的边的 weight*order/sumWeight。weight 是边的权重，默认为 1，order 是边的上层节点在上层的排序，sumWeight 是关联边的权重总和。
然后我们就可以执行一系列迭代尝试改进这个顺序，直到找到一个满意的解时停止迭代。
启发式迭代：
biasRight：重心相等时索引小的左偏还是右偏
downLayerGraphs：从上到下分层，n 行根据 n - 1 行排序
upLayerGraphs：从下到上分层，n 行根据 n + 1 行排序
重心相等时索引小的左偏的情况下，先从下到上分层扫描，排序；再进行从上到下分层扫描，排序；
重心相等时索引小的右偏的情况下，先从下到上分层扫描，排序；再进行从上到下分层扫描，排序；
每次排序后都会计算交叉点个数，如果交叉个数更好了，则替换节点矩阵，然后再进行上述的 4 边扫描，直到上述 4 遍扫描后都没有再取得更优解，迭代结束。
A->B;
A->C;
A->F
B->E;
C->D;
C->G;
F->D;原始图:
第一次迭代：从下到上分层扫描，左偏
crossCount = 1
第二次迭代：再进行从上到下分层扫描，左偏
crossCount = 1
第三次迭代：从下到上分层扫描，右偏
crossCount = 0
获得了更优解，这个迭代周期结束，重新开始一个迭代周期，在这个迭代周期都没有再找到更优解，迭代结束
输出矩阵:
[[A],
[25, 27, 26],
[B, F, C],
[28, 31, 29, 30],
[E, D, G]
]下面是上述过程的代码：
function order(g) {var maxRank = util.maxRank(g),
downLayerGraphs = buildLayerGraphs(g, _.range(1, maxRank + 1), "inEdges"), // 从上到下分层，n 行根据 n - 1 行排序
upLayerGraphs = buildLayerGraphs(g, _.range(maxRank - 1, -1, -1), "outEdges"); // 从下到上分层，n 行根据 n + 1 行排序
var layering = initOrder(g);
assignOrder(g, layering);
var bestCC = Number.POSITIVE_INFINITY,
best;
for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) {sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2); // 扫描按权重排序
layering = util.buildLayerMatrix(g); // 节点 id 的矩阵
var cc = crossCount(g, layering); // 返回当前矩阵下交叉点个数
if (cc < bestCC) {
lastBest = 0;
best = _.cloneDeep(layering);
bestCC = cc;
}
}
assignOrder(g, best);
}计算顶点坐标：
节点的层号和层内序号确定后, 布局结果的基本框架就已经确定了. 一般有向图可以采用在垂直方向或者水平方向按序号递增的方式分别分配纵坐标和横坐标。
实际应用场景
1、依赖关系：
可视化项目依赖，组件依赖关系：比如打包编译依赖的时候，把各种包的依赖关系按照拓扑序列排序，先引入排在前面的包，后引入排在后面的包。
2、调度流程：
自动化布局 UML 图，workflow 等。
事项流程：
spark 任务执行：大规模数据处理计算引擎
UML 类图
儿茶酚胺合成代谢路径
3、决策树：鄙视链案例 - 婚姻市场中的房市
4、复杂人物关系链分析：红楼梦
参考资料：
http://jgaa.info/accepted/200…
http://www.jos.org.cn/jos/ch/…
http://leungwensen.github.io/…
