深入理解树的重心（Python树重心算法详解）

为什么需要找树的重心？

在很多高级算法中，比如点分治（Centroid Decomposition），都需要先找到树的重心。通过重心分解，可以将树的问题转化为更小的子问题，从而降低时间复杂度。这也是为什么树结构重心分解成为算法工程师必须掌握的技能之一。

算法思路

要找到树的重心，我们可以使用深度优先搜索（DFS）：

1. 任选一个节点作为根（通常选0或1）。
2. 通过 DFS 计算每个子树的大小（节点数量）。
3. 对于每个节点 u，计算删除 u 后最大连通块的大小：
       max( n - size[u], max(size[v]) )，其中 v 是 u 的子节点。
4. 使这个最大值最小的节点就是重心。

Python 实现代码

下面是一个完整的、可运行的 树的重心求解 Python 代码：

def find_tree_centroid(n, edges):    from collections import defaultdict        # 构建邻接表    graph = defaultdict(list)    for u, v in edges:        graph[u].append(v)        graph[v].append(u)        size = [0] * n          # 子树大小    max_subtree = [0] * n   # 删除该节点后最大子树的大小    visited = [False] * n        def dfs(u, parent):        size[u] = 1        max_size = 0        for v in graph[u]:            if v != parent:                dfs(v, u)                size[u] += size[v]                max_size = max(max_size, size[v])        # 上方连通块的大小为 n - size[u]        max_subtree[u] = max(max_size, n - size[u])        dfs(0, -1)  # 从节点0开始DFS        # 找到 max_subtree 最小的节点    min_val = min(max_subtree)    centroids = [i for i in range(n) if max_subtree[i] == min_val]    return centroids# 示例：构建一棵树n = 7edges = [(0,1), (1,2), (1,3), (0,4), (4,5), (4,6)]centroids = find_tree_centroid(n, edges)print("树的重心节点为:", centroids)

代码解析

• graph：使用邻接表存储无向树。
• size[u]：以 u 为根的子树包含的节点数。
• max_subtree[u]：删除 u 后，所有连通块中最大的节点数。
• DFS 过程中，我们同时计算子树大小和最大连通块大小。
• 最后遍历所有节点，找出使 max_subtree 最小的节点，即为重心。

总结

通过本教程，你已经学会了如何用 Python 实现树的重心求解。这项技能在处理树形动态规划、点分治等高级算法时非常有用。记住，理解算法背后的逻辑比死记代码更重要。

希望这篇关于Python树重心算法的教程对你有帮助！如果你正在准备算法面试或参加编程竞赛，不妨多练习几遍这个经典模板。

关键词回顾：Python树重心算法、树的重心求解、图论算法Python实现、树结构重心分解