深入理解树的重心（Rust树重心算法详解：小白也能掌握的图论基础）

为什么需要找树的重心？

树的重心在很多高级算法中有重要作用，比如：

• 点分治（Centroid Decomposition）——用于高效处理树上路径问题
• 优化树形 DP 的复杂度
• 构建更平衡的树结构

掌握 Rust图论算法 中的重心查找，是你进阶算法能力的重要一步。

算法思路

要找到树的重心，我们可以使用一次 DFS（深度优先搜索）遍历整棵树，并在回溯过程中计算每个子树的大小。对于每个节点 u，我们记录：

• subtree_size[u]：以 u 为根的子树包含的节点总数
• max_subtree[u]：删除 u 后，所有连通块中最大的节点数

注意：删除 u 后，除了它的各个子树，还有一个“父方向”的连通块，大小为 n - subtree_size[u]。

因此，max_subtree[u] = max( n - subtree_size[u], max(subtree_size[v] for v in children of u) )

我们的目标是找到使 max_subtree[u] 最小的节点 u。

Rust 实现代码

下面是一个完整的、易于理解的 Rust 实现。我们使用邻接表存储树，并通过递归 DFS 计算重心。

use std::collections::HashMap;use std::cmp;/// 查找树的重心fn find_centroid(    graph: &HashMap<i32, Vec<i32>>,    n: usize,) -> i32 {    let mut visited = vec![false; n + 1];    let mut subtree_size = vec![0; n + 1];    let mut min_max_sub = n + 1;    let mut centroid = 1;    fn dfs(        u: i32,        parent: i32,        graph: &HashMap<i32, Vec<i32>>,        visited: &mut Vec<bool>,        subtree_size: &mut Vec<usize>,        n: usize,        min_max_sub: &mut usize,        centroid: &mut i32,    ) {        visited[u as usize] = true;        subtree_size[u as usize] = 1;        let mut max_sub = 0;        for &v in &graph[&u] {            if v != parent {                dfs(v, u, graph, visited, subtree_size, n, min_max_sub, centroid);                subtree_size[u as usize] += subtree_size[v as usize];                max_sub = cmp::max(max_sub, subtree_size[v as usize]);            }        }        // 父方向的连通块大小        max_sub = cmp::max(max_sub, n - subtree_size[u as usize]);        if max_sub < *min_max_sub {            *min_max_sub = max_sub;            *centroid = u;        }    }    dfs(        1,        -1,        graph,        &mut visited,        &mut subtree_size,        n,        &mut min_max_sub,        &mut centroid,    );    centroid}fn main() {    // 构建一个简单的树：1-2, 1-3, 2-4, 2-5    let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();    let edges = vec![(1, 2), (1, 3), (2, 4), (2, 5)];    for (u, v) in edges {        graph.entry(u).or_insert_with(Vec::new).push(v);        graph.entry(v).or_insert_with(Vec::new).push(u);    }    let n = 5;    let centroid = find_centroid(&graph, n);    println!("树的重心是: {}", centroid);}

代码解析

这段代码实现了标准的树重心查找算法：

1. 使用 HashMap<i32, Vec<i32>> 存储无向树的邻接表
2. dfs 函数递归计算每个节点的子树大小
3. 在回溯时，计算删除当前节点后最大连通块的大小
4. 更新全局最优解（即重心）

注意：我们假设节点编号从 1 开始，总节点数为 n。这是常见的竞赛设定。

学习建议

如果你刚开始学习 Rust编程教程，建议你：

• 先理解递归和 DFS 的基本思想
• 手动模拟一遍小树的执行过程（比如 5 个节点）
• 尝试修改代码，让它返回所有重心（有些树有两个）

总结

通过本文，你已经掌握了 树的重心求解 的核心思想和 Rust 实现方法。树的重心是图论中的基础工具，后续学习点分治等高级算法时会频繁用到。希望这篇教程能帮助你在 Rust图论算法 的道路上迈出坚实的一步！

关键词回顾：Rust树重心算法、Rust图论算法、Rust编程教程、树的重心求解。