基于层次网络的最大流求解方法
第1O卷第4期
2010年8月
潍坊学院学报
JournalofWeifangUniversity
V0l_10NO.4
Aug.2010
基于层次网络的最大流求解方法
徐翠霞
(潍坊学院,山东潍坊261061)
摘要:针对最大流问题的研究现状,提出了分层求解最大流的简单方法,并给出了该方法可行的严
格证明.该方法首先求得层次网络的阻塞流,进而最终求得一个最大流.另外,该方法还针对有向流网络
的特点,将算法中涉及的流网络,剩余网络和层次网络共用一个网络结构,既有效地降低了算法的空间复
杂度,还大大提高了算法的执行效率.
关键词:剩余网络;层次网络;饱和弧;最大流;阻塞流
中图分类号:TP301文献标识码:A文章编号:1671—4288(2010)04—0042—04
1基本概念
1.1有向流网络
一
个有向流网络N一(G,S,t,C)是一个四元组,其中,G一(V,E)是一个具有n个顶点,m条弧的有向
图;V是n个顶点的非空有限集合;E是m条弧的非空有限集合;S和t是G的两个特殊顶点,分别称为源
点和汇点,S?V,t?V;C是一个E一的函数,R是正实数集合,即每条弧e(e?E)都赋有一个非负的容
量C(e).
1.2顶点的层次和层次网络
顶点v的层次,记为level(v),是从源点S到顶点v路径中边的最小数,给定一个有向图G一(V,E),
层次网络I为(V,E),其中E一{<u,v>}jlevel(v)一level(u)+1}.
1.3弧容量,弧流量和剩余流量
在有向流网络中,每条弧e(e?E)上的非负容量C(e),称为该弧的弧容量,而实际通过该弧
的流量f(e),称为弧流量,弧容量是允许通过该弧的最大流量,然,弧流量不超过弧容量.弧容量和弧流
量之差为该弧的剩余流量,记为r(e).
1.4可行流和最大流
有向流网络中的一个可行流f,它一方面赋予网络中的每一条弧e(e
?E)一个非负流量f(e),另一方
面还满足两个规则.
(1)容量规则
f(e)?C(e)
对于有向流网络中的每条弧e(e?E),其弧流量f(e)不超过其弧容量C(e).
(2)守恒规则
IN(f,v)一OUT(f,v),其中v?V,{s,t}
除源点和汇点外的其余顶点的输人量IN(f,v)等于输出量()UT(f,v).
()UT(f,s)一IN(f,t)
源点的输出量等于汇点的输入量.(注意,源点的输入量和汇点的输出量均为0)
一
个可行流f的流量为源点的输出量或汇点的输入量,分别
示为:
*收稿日期:2O10—0312
基金项目:潍坊市2009年科学技术发展计划(20090l129)
作者简介:徐翠霞(】973一),女,山东雄坊人,潍坊学院计算机与通信工程学院副教授,工学硕士.研究方向:算法设
计与分析.
——
42--——
第4期徐翠霞:基于层次网络的最大流求解方法
value(f)一OUT(f,s)或value(f)一IN(f,t)
设f是可行流,若对任何其他可行流f,均有value(f)~value(f,),则f是最大流.
1.5可行流中弧的种类
(1)饱和弧和非饱和弧
在一个可行流f中,若一条弧e(e?E)满足f(e)一C(e),则称该弧为饱和弧.若一条弧e(eEE)
满足f(e)<C(e),称该弧为非饱和弧.
(2)零流量弧和非零流量弧
在一个可行流f中,若一条弧e(e?E)满足f(e)一0,则称该弧为零流量弧.若一条弧e(e?E)
满足f(e)>O,称该弧为非零流量弧.
1.6阻塞流
设G一(V,E)是一个具有n个顶点,m条弧的有向图,L是包含顶点S和t的G的子图,L中的流f称
为关于L的阻塞流,如果在L中每一条从S到t的路径中都至少有一条饱和弧.
1.7剩余网络
已知一个有向流网络和一个可行流,可行流的剩余网络与原始网络有相同的顶点,原始网络中的每条
弧在剩余网络中对应两条弧.定义如下:对于原始网络中的每条弧<u,v>,令f(u,v)为弧流量,c(u,v)为
弧容量.如果f(U,v)>0,则剩余网络中包含一条流量为f的弧<v,u>;如果f(u,v)<c(u,v),则剩余网
络中包含一条流量为c—f的弧<u,v>.
2算法的基本思想
2.1最大流的分层计算方法
首先初始化流为零流量,并设网络的剩余网络R为原始图,然后分阶段进行,每一阶段由两步组成.
(1)根据剩余网络R计算层次网络L,如果t不在L中,则算法停止,否则继续;
(2)计算L上的阻塞流,即只要在L中存在S到t的路径P,就用P对当前的可行流进行增值,并相应
地修改剩余网络R和层次网络I.
注意,增广路径在同一层次网络中具有相同长度,而且,在第一阶段后的任一阶段的增广路径都严格
地比它前面阶段的路径长.一旦t在新构造的层次网络中不出现,算法就立即终止.
2.2层次网络的计算方法
首先初始化各顶点的层次为一l,然后进行如下操作:
Step1:初始化源点S的层次为0,即levelEs]一0;
Step2:调用广度优先遍历算法,执行一步遍历操作,设当前遍历的弧为<v,v.>,令r(v,v)为该弧
的剩余流量.若r(v,v.)>O,则执行如下操作:
?若v还没有遍历,则levelEv.]一level[-v1]+1,且将弧<v1,v2>JJH人到L中;
?若v2已遍历且level[v.]一level[-v]+1,则将弧<v,v.>an人到L中;
?否则,不能将弧<v,v>加入到L中.
算法执行后,如果某顶点的层次为一1,表示该顶点不在层次网络L中,否则,该顶点在层次网络L
中.
2.3阻塞流的计算方法
在层次网络中搜索从S到t的增广路径,既可以使用BFS搜索,也可以DFS搜索.可以在找到了一
条增广路径后停止图搜索,进行增广运算,然后重新启动搜索;也可以继续搜索,并找到另一条路径,重复
进行,直到无路径为止.
为了提高算法的执行效率,在此选择第二种途径利用DFS搜索实现层次网络上阻塞流的计算.具体
操作如下:
while(t为L中的顶点){
for(u—S;u!一t&&S有出弧未访问;){
if(u有出弧<u,v>未访问){//前进
一
43—
潍坊学院学报2010年8月
?将<u,v>添入路径P中;
?u—v;
)
else{//后退
?删除I和U的所有邻接边;
?删除路径P中最末一条边;
?将u设为路径P中最后一个顶点.
(注意U可能是s);
}
if(u一一t){//增值
?计算P的瓶颈容量?;
?更新G中的流f,即将f增加?;
?更新R和I,删除饱和边;
?将U设为路径P中最后一个顶点.
(注意U可能是s);
)
)//for
}//while
3算法选择的数据结构
为了实现最大流算法,在此使用流网络的
邻接表表示,这是通过
扩展常用的邻接表得来的.
(1)让每条边关联两个权重,cap(弧容量)和flow(弧流量).
(2)虽然流网络是有向图,而算法需要从两个方向遍历边,所以使用针对无向图的类似表示:如果从U
到v有一条边,容量为C,流量为f,也可以有一条从v到u的边,容量为一C,流量为一f.如此以来,不需要
显式地构造剩余网络,使用一个简单的宏即可.
#defineQ(e一>cap<07一e一>flow:e一>flow)
(3)为了避免过多的表遍历,还运用了连接表示每条边的两个表节点的链接,当更改一个地方的流量
时,另一个地方的流量也会被更新.
(4)由于L是G的子图,可以隐式地构造层次网络,将G中的每一条弧增加一个标识位,如果该弧加
入I,即置为true,否则置为false.
typedefstruetnode*link;
structnode{
//弧头顶点
,,弧容量
//弧流量
//指向反方向的弧
//指向下一条弧
//该弧是否已加入I中
ff顶数
//弧数
}f谖轰
;
m;明
一一,,,一;一,,一;一一s算4
第4期徐翠霞:基于层次网络的最大流求解方法
引理1算法计算的层次网络至多为n个.
为了证明此算法计算的层次网络至多为n个,首先证明算法中增广路径的长度序列是严格递增的.
设P为当前层次网络中的任意增广路径,在用P增值后,至少有一条边将饱和,并在剩余图中消失.同时,
至多有lPJ条新边将在剩余图中出现,但它们是回边,因此不会对从s到t的最短路径做出贡献.因为
每次有一条边在层次网络中消失,因此最多可能有m条长度为IPf的路径.当t在层次网络中再也不能
从S到达时,任何增广路径必须用一条回边或交叉边,并且因此一定具有严格大于IPI的长度.因为任
何增广路径的长度介于1到n,1之间,用做增值的层次网络个数最多为n一1个,因为t不出现的层次网
络也要计算一次,因此计算的层次网络总数最多是n.
5算法运行时间分析
利用广度优先搜索,计算每一个层次网络L,需要的时问均为O(m);
在每一个L上计算阻塞流的时间
为0(ran).分析如下:
(1)因为在每一次增值时,至少删除层次网络的一条边,因此增值次数至多是m.每次增值耗费o(n)
时间,用以修改流量,因此每一阶段增值的总耗费是O(mn).
(2)因为每一次后退将导致除S或t外的一个顶点被删除,因此后退的次数(即for语句的else部分)
最多是n一2.在后退中,从层次网络中删除的边的总数至多是m,这意味着在每一个阶段中,后退的总耗
费为O(m+n).
(3)在每次增值或后退前的向前次数(for语句的if部分)不能超过n—l;否则,在增值或后退前有一个
顶点将不止一次被访问.因此在每一阶段,前进的总数为O(mn).
每一阶段的总耗费为0(mn),因为最多有n个阶段,因此该算法的总运行时间为O(mn).
6结论
该方法不仅合理使用BFS搜索和DFS搜索分别求解层次网络及其上的阻塞流,进而最终求得一个最
大流;针对流网络的特点,将算法中涉及的流网络,剩余网络和层次网络共用一个网络结构,既有效地降低
了算法的空问复杂度,还大大提高了算法的执行效率.
参考文献:
[1]KolmanB,BusbyRC,RossSC.DiscreteMathematicalStructuresEM].北
京:高等教育出版社,2001
[2~RobertSedgewick.C算法:第二卷(图算法)EM].周良忠,译.3版.北
京:人民邮电出版社,2004.
[3]王晓东.算法
与分析EM].北京:清华大学出版社,2003.
ASimpleAlgorithmofMaximumFlowBasingonLayerNetwork
XUCui—xia
(WeifangUniversity,Weifang261061,China)
Abstract:Inordertosolvetheproblemofmaximumflows,anewfeasibilityapproachwasproposedac—
cordingtothepresentresearchsituation.Thismethodusedtofindblockflowsinlayernetworks,and
thenfinallyfindamaximumflow.Itisprovedthatthemethodisefficientandfeasible.Itcanhelpteach—
ingimprovementandpracticeapplication.Itisalsoworthpopularization.
Keywords:residualnetwork,layernetwork,saturationedge,maximumflow,blockflow
(责任编辑:肖恩忠)