Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第2 版)
210
8
8.2.1 输入 / 输出
对于
E
中的每条边
(
u, v
)
Ford-Fulkerson
算法会计算出整数流量
f
(
u, v
)
,用于表示流
经边
(
u, v
)
的单位流量。算法在结束时,还会顺道计算出网络的最小割,即由边集
组成一个“瓶颈”,来防止更多的单元在网络中从
s
流向
t
8.2.2 决方案
这里介绍的
Ford-Fulkerson
算法实现采用了链表存储边。每个顶点
u
维护着两个不同
的列表:从
u
发出的前向边和指向
u
的后向边,因此每条边都会在这两个列表中出现。
本书的代码库中包含了一个使用二维数组存储边的算法实现,这个数据结构更适用于稠
密的流网络图。
Ford-Fulkerson
算法
依赖于如下结构:
FlowNetwork
代表网络流问题。这个抽象类有两个子类一个基于邻接表,另一个基于邻接矩阵。
getEdgeStructure()
法会返回边集的底层存储结构。
VertexStructure
为顶点维护两个链表(前向和后向),分别为从顶点离开的边和进入顶点的边。
EdgeInfo
在网络流中记录边的信息。
VertexInfo
记录搜索到的增广路径。
VertexInfo
会记录增广路径之前的顶点,以及它是被前向
边还是后向边访问到的。
Ford-Fulkerson 算法小结
最好情况、平均情况和最坏情况:
O
(
E
*
mf
)
compute (G)
while exists augmenting path in G do
processPath (path)
end
processPath ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221