图论动画-流分解

null15.082 和 6.855J 15.082 和 6.855J 流分解nullbegin 初始化 while y   do begin Select(s, y) Search(s, y) if 发现圈 C then do begin 令 D = Capacity(C, y) 添加 Flow(D, C)到圈流中 从 y 减去 Flow(D, C) end if 找到路径 P then do begin 令 D = Capacity(P, y) 添加 Flow(D, P) 到路径流中 从 y 减去 Flow(D, P) end end初始流初始流 12453623473448592-20000供应结点需求结点平衡结点流 x寻找路径或圈寻找路径或圈12453623473448592-200选择一供应结点1实施深度优先搜索，直到发现圈或路径判定其容量容量是 2更新分解更新分解12453623473448592-200把圈流加到分解中1更新当前流圈流路径流环绕1-2-4-5-3-1 的 2 单位的流25670寻找下一路径或圈寻找下一路径或圈124536334452-200从供应结点开始，寻找下一圈或路径1圈流路径流环绕1-2-4-5-3-1 的 2 单位的流2567更新分解和当前流更新分解和当前流124536334452-200更新当前流和分解1圈流路径流环绕1-2-4-5-3-1 的 2 单位的流2567环绕 2-4-5-3-2 的3单位的流0 234寻找下一流或圈寻找下一流或圈12453634452-200从供应结点开始寻找下一圈或路径1圈流路径流22344-5-3-4 的容量是 3环绕1-2-4-5-3-1 的 2 单位的流环绕 2-4-5-3-2 的3单位的流更新更新12453634452-2001圈流路径流2234更新当前流和分解0112 单位环绕 1-2-4-5-3-1 的 3 单位环绕 2-4-5-3-23 单位环绕 4-5-3-4寻找下一流或圈寻找下一流或圈11245363452-2001圈流路径流2241从供应结点开始寻找下一流或圈1-2-4-6的容量是 22 单位环绕 1-2-4-5-3-13 单位环绕 2-4-5-3-23 单位环绕 4-5-3-4更新更新11245363452-2001圈流路径流2241更新当前流和分解001002 单位在 1-2-4-6 上2 单位环绕 1-2-4-5-3-13 单位环绕 2-4-5-3-23 单位环绕 4-5-3-4寻找下一路径或弧寻找下一路径或弧1124536450-200圈流路径流41100开始于任何和有流的弧相邻的结点，找到下一流或圈。32 单位在 1-2-4-6 上2 单位环绕 1-2-4-5-3-13 单位环绕 2-4-5-3-23 单位环绕 4-5-3-4更新更新1124536450-200圈流路径流41100300402 单位在 1-2-4-6 上2 单位环绕 1-2-4-5-3-13 单位环绕 2-4-5-3-23 单位环绕 4-5-3-41 单位环绕 3-4-6-5-3最后的分解最后的分解12453640-200圈流路径流004002 单位在 1-2-4-6 上2 单位环绕 1-2-4-5-3-13 单位环绕 2-4-5-3-23 单位环绕 4-5-3-41 单位环绕 3-4-6-5-34 单位环绕 5-6-5