一、boykov_kolmogorov_max_flow 是什么？

1. 定义

Boykov–Kolmogorov（BK）算法是一种针对小割（min-cut）问题高度优化的最大流算法，特别适合稠密图与局部更新频繁的场景。

在 Boost.Graph 中：

boost::boykov_kolmogorov_max_flow(g, s, t, ...)

用于求解：

• 最大流（max-flow）
• 最小割（min-cut）（隐式得到）

---

1.2 算法背景

BK 算法最早用于：

• 计算机视觉

  • Graph Cut 图像分割
  • Stereo matching

• 机器人

  • Occupancy / semantic segmentation
  • 能量最小化问题

与 Dinic / Push-Relabel 相比：

算法	优势
Dinic	理论清晰，通用
Push-Relabel	大规模稀疏图
Boykov–Kolmogorov	小割、局部更新、视觉问题最强

---

二、算法数学模型

2.1 最大流问题

给定有向图 ( $G=(V,E)$ )，容量 ( $c(e)$ )：

$$\max \sum _{(s,v)\in E}f(s,v)$$

满足：

• 容量约束 ( $0\le f(e)\le c(e)$ )
• 流守恒

---

2.2 最小割等价性

$$\max \text{-flow}=\min \text{-cut}$$

BK 算法内部维护：

• 从 source 扩展的搜索树
• 从 sink 扩展的搜索树
• 在“相遇”时增广

---

三、Boost.Graph 接口详解

3.1 函数签名（常用版本）

template <
    class Graph,
    class CapacityEdgeMap,
    class ResidualCapacityEdgeMap,
    class ReverseEdgeMap,
    class VertexIndexMap,
    class ColorMap
>
typename property_traits<CapacityEdgeMap>::value_type
boykov_kolmogorov_max_flow(
    Graph& g,
    typename graph_traits<Graph>::vertex_descriptor s,
    typename graph_traits<Graph>::vertex_descriptor t,
    CapacityEdgeMap capacity,
    ResidualCapacityEdgeMap residual_capacity,
    ReverseEdgeMap reverse_edge,
    VertexIndexMap vertex_index,
    ColorMap color
);

---

3.2 每个参数的真实含义

参数	作用
g	图
s	源点（source）
t	汇点（sink）
capacity	edge_capacity_t
residual_capacity	edge_residual_capacity_t
reverse_edge	edge_reverse_t
vertex_index	顶点索引
color	顶点状态（算法内部使用）

BK 算法强依赖 edge_reverse 与 residual graph。

---

四、标准 Graph 类型定义（工程模板）

using Traits = boost::adjacency_list_traits<
    boost::vecS, boost::vecS, boost::directedS>;

using Graph = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    boost::property<boost::vertex_index_t, int,
    boost::property<boost::vertex_color_t, boost::default_color_type>>,
    boost::property<boost::edge_capacity_t, double,
    boost::property<boost::edge_residual_capacity_t, double,
    boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>
>;

---

五、构图关键：必须成对加边

5.1 正确加边方式（核心）

auto add_edge_pair = [&](int u, int v, double cap) {
    auto e1 = add_edge(u, v, g).first;
    auto e2 = add_edge(v, u, g).first;

    capacity[e1] = cap;
    capacity[e2] = 0.0;

    reverse_edges[e1] = e2;
    reverse_edges[e2] = e1;
};

错误做法：只加一条边
错误做法：反向边没绑定

---

六、完整示例

Graph g(4);

auto capacity = get(boost::edge_capacity, g);
auto residual = get(boost::edge_residual_capacity, g);
auto reverse  = get(boost::edge_reverse, g);
auto index    = get(boost::vertex_index, g);
auto color    = get(boost::vertex_color, g);

add_edge_pair(0, 1, 3);
add_edge_pair(0, 2, 2);
add_edge_pair(1, 2, 1);
add_edge_pair(1, 3, 2);
add_edge_pair(2, 3, 4);

double maxflow = boost::boykov_kolmogorov_max_flow(
    g, 0, 3,
    capacity, residual, reverse, index, color
);

std::cout << "Max flow = " << maxflow << std::endl;

---

七、如何得到最小割？

BK 算法执行后：

• source 侧可达顶点
• sink 侧不可达顶点

for (auto v : boost::make_iterator_range(vertices(g))) {
    if (color[v] == boost::white_color) {
        // 在 source side
    } else {
        // 在 sink side
    }
}

这正是 Graph Cut 图像分割的标签结果。

---

八、工程级注意事项

8.1 residual_capacity 必须存在

即使你不显式初始化：

residual[e] = capacity[e];

BK 内部会更新它。

---

8.2 color_map 不能复用

多次调用前必须重置：

for (auto v : vertices(g))
    color[v] = boost::white_color;

---

8.3 图规模建议

场景	建议
图像分割	BK（首选）
大规模稀疏网络	Dinic
通用流	Push-Relabel

---

九、与视觉 / SLAM 的关系

问题	BK 的角色
图像前景/背景分割	最小割
语义地图	标签优化
路径规划	能量最小化
SLAM 中的 data association	二值优化

BK ≈ 能量最小化的工业级利器

---

总结

• boykov_kolmogorov_max_flow 是 Boost 中最适合小割/视觉问题的最大流算法
• 必须使用 reverse edge + residual graph
• 构图正确性 > 算法本身
• 能直接得到 max-flow + min-cut
• 在机器人与视觉领域非常实用

---