Dinic 算法中的层级图代表什么？

Question

我明白残差图是什么了。但是水平图是什么意思呢？ http://en.wikipedia.org/wiki/Dinic%27s_algorithm

Answer 1

来自维基百科文章，层级图是残差图带边的子图

E_L = {(u, v) in E_f : dist(v) = dist(u) + 1},

其中E_f是残差图中的边集，dist(w)是源s到w的未加权距离。

在英语中，E_L 由残差图的边组成，这些边属于来自 s 的一些未加权的最短路径。

Answer 2

在级别图中两个顶点之间的边具有相同的距离标签不被保留。在网络流中，我们使用 BFS 来查找级别图。

我们还删除了无法到达汇点的顶点以及无法从源点到达的顶点。