August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
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,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
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.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.