首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》解决方案

关灯直达底部

Ford-Fulkerson基于如下结构:

FlowNetwork

表示这个网络流问题。这个抽象类可以有两种实现,一种基于邻接表,另外一种使用数组。getEdgeStructure方法返回的是存储边集的结构。

VertexStructure

为顶点维护两个链表,分别存储的是前向边和后向边。

EdgeInfo

在网络流中记录边的信息。

VertexInfo

在数组中记录搜索到的增广路,增广路的前部节点和这个节点是否有一个前向边或者后向边。

例8-1是Ford-Fulkerson的一个实现,其流程如图8-4所示。一个可配置的Search对象能够计算出网络中的增广路,在容量限制内向网络中加入更多的流。如果在之前迭代的过程中做出的是次优决定,那么Ford-Fulkerson的搜索将会继续,但是不需要撤销之前的工作。

图 8-4 Ford-Fulkerson的建模信息

例8-1:Ford-Fulkerson Java实现

任何自图8-5的抽象Search类扩展出的搜索方法都能够用来寻找一条增广路。Ford-Fulkerson的原始版本是使用深度优先搜索,不过Edmonds-Karp使用的是广度优先搜索(见第6章)。

图 8-5 Search的功能

例8-3的流网络是使用深度优先搜索寻找增广路得到的结果,例8-2是其实现。路径使用栈来存储顶点。我们从栈中弹出一个顶点u,然后找到u的一个未访问顶点v,且满足这样两个条件:(i)边(u,v)是一条前向边并且还有多余的容量;(ii)边(v,u)是一条前向边,并且通过这条边的流可以减少。那么我们就能够找到一条潜在的增广路。最后,我们达到了汇点t,这样就找到了一条增广路径,或者路径为空,表示没有增广路。

例8-2:使用深度优先搜索来寻找增广路

顶点之间的后向指针由VertexInfo结构来维护,这样FordFulkerson.processPath方法能够遍历这条增广路。

广度优先搜索的实现,又名Edmonds-Karp算法,其实现见例8-3。在搜索过程中,路径的结构是顶点组成的队列。我们从队列头移除顶点u,然后将可能组成增广路径的邻接顶点加入到队列尾部,这就是我们扩展潜在增广路径的方式。同样,我们达到了汇点t,这样就找到了一条增广路径,或者路径为空,表示没有增广路,此时算法结束。我们使用图8-3的流网络,使用广度优先搜索能够找到4条增广路,分别是<s,1,3,t>,<s,1,4,t>,<s,2,3,t>和<s,2,4,t>。也得到了相同的最大流。

例8-3:使用广度优先搜索来寻找增广路径