Rust语言实现最小割算法（从零开始掌握Rust图论与网络流编程）

什么是最大流最小割定理？

简单来说：在一个有向图中，从源点 s 到汇点 t 的最大流值等于分离 s 和 t 的最小割容量。

• 最大流：从源点能“推送”到汇点的最大流量。
• 最小割：删除一组边后，使源点和汇点不再连通，且这组边的总容量最小。

因此，只要我们能计算出最大流，就能间接得到最小割！

准备工作：创建 Rust 项目

首先，在终端中执行：

cargo new min_cut_rustcd min_cut_rust

我们不需要额外依赖，纯标准库即可实现。

步骤一：定义图的数据结构

我们将使用邻接表表示图，并用二维数组存储残量图（Residual Graph）。

struct Graph {    // 残量图：capacity[u][v] 表示从 u 到 v 的剩余容量    capacity: Vec<Vec<i32>>,    n: usize, // 节点数量}impl Graph {    fn new(n: usize) -> Self {        Graph {            capacity: vec![vec![0; n]; n],            n,        }    }    fn add_edge(&mut self, u: usize, v: usize, cap: i32) {        self.capacity[u][v] = cap;    }}

步骤二：实现 Edmonds-Karp 最大流算法

该算法使用 BFS 寻找增广路径，直到无法再找到为止。

use std::collections::VecDeque;impl Graph {    fn bfs(&self, s: usize, t: usize, parent: &mut Vec<usize>) -> bool {        let mut visited = vec![false; self.n];        let mut queue = VecDeque::new();                queue.push_back(s);        visited[s] = true;        parent[s] = usize::MAX; // 标记源点无父节点        while let Some(u) = queue.pop_front() {            for v in 0..self.n {                if !visited[v] && self.capacity[u][v] > 0 {                    queue.push_back(v);                    parent[v] = u;                    visited[v] = true;                    if v == t {                        return true;                    }                }            }        }        false    }    fn max_flow(&mut self, s: usize, t: usize) -> i32 {        let mut parent = vec![0; self.n];        let mut max_flow = 0;        while self.bfs(s, t, &mut parent) {            let mut path_flow = i32::MAX;            let mut v = t;            while v != s {                let u = parent[v];                path_flow = path_flow.min(self.capacity[u][v]);                v = u;            }            v = t;            while v != s {                let u = parent[v];                self.capacity[u][v] -= path_flow;                self.capacity[v][u] += path_flow; // 反向边                v = u;            }            max_flow += path_flow;        }        max_flow    }}

步骤三：从最大流推导最小割

最大流计算完成后，残量图中从源点 s 可达的节点集合为 S，其余为 T。所有从 S 指向 T 的原始边即为最小割边集。

impl Graph {    fn find_min_cut(&self, s: usize, original_capacity: &Vec<Vec<i32>>) -> Vec<(usize, usize)> {        // 在残量图中从 s 进行 BFS，找到所有可达节点（属于集合 S）        let mut visited = vec![false; self.n];        let mut queue = VecDeque::new();        queue.push_back(s);        visited[s] = true;        while let Some(u) = queue.pop_front() {            for v in 0..self.n {                if !visited[v] && self.capacity[u][v] > 0 {                    visited[v] = true;                    queue.push_back(v);                }            }        }        // 收集所有从 S 到 T 的原始边（即最小割）        let mut cut_edges = Vec::new();        for u in 0..self.n {            for v in 0..self.n {                // u 在 S 中，v 在 T 中，且原始图中存在边                if visited[u] && !visited[v] && original_capacity[u][v] > 0 {                    cut_edges.push((u, v));                }            }        }        cut_edges    }}

步骤四：整合主函数并测试

fn main() {    let n = 6; // 节点数：0~5，其中 0 是源点，5 是汇点    let mut graph = Graph::new(n);    // 构建图（示例）    graph.add_edge(0, 1, 16);    graph.add_edge(0, 2, 13);    graph.add_edge(1, 2, 10);    graph.add_edge(1, 3, 12);    graph.add_edge(2, 1, 4);    graph.add_edge(2, 4, 14);    graph.add_edge(3, 2, 9);    graph.add_edge(3, 5, 20);    graph.add_edge(4, 3, 7);    graph.add_edge(4, 5, 4);    // 保存原始容量用于后续找最小割    let original_capacity = graph.capacity.clone();    let max_flow = graph.max_flow(0, 5);    println!("最大流: {}", max_flow);    let min_cut = graph.find_min_cut(0, &original_capacity);    println!("最小割边集: {:?}", min_cut);    // 输出示例：[(1, 3), (4, 5)]}

总结

通过本教程，你已经掌握了如何在 Rust 中实现 最小割算法。核心思路是：

1. 构建残量图；
2. 使用 Edmonds-Karp 算法计算最大流；
3. 在残量图中从源点 BFS 找出可达集合 S；
4. 遍历原始图，找出从 S 到 T 的边，即为最小割。

这项技能不仅让你深入理解了 Rust图算法实现，也为学习更复杂的 Rust网络流编程 打下坚实基础。记住，最大流最小割定理 是连接流与割的桥梁，掌握它，你就掌握了图论中的一把金钥匙！

现在，尝试修改图的结构或添加更多边，看看最小割如何变化吧！