求无向无环简单图最优节点均衡分割的算法问询

首先得明确：你说的无向无环连通图本质就是树，这个问题核心是找到树中能把节点分成最均衡两部分的那条边——让分割后较大子树的节点数尽可能小。

核心思路 #

树的每条边都对应唯一的一对子树：当你把树看作有根结构时，每个非根节点和它父节点的边被砍掉后，会把树拆成「该节点的子树」和「剩下的所有节点」两部分。所以我们只需要计算每个子树的大小，再对每个子树计算max(子树大小, N-子树大小)，找到这些值里的最小值就行。

具体步骤 #

• 步骤1：构建邻接表
  把树的节点和边转换成邻接表形式，方便后续遍历。比如用数组或字典存储每个节点的相邻节点。
• 步骤2：后序DFS计算子树大小
  任选一个节点作为根（比如节点0），用后序遍历递归计算每个节点的子树大小：每个节点的子树大小 = 1（自身） + 所有子节点的子树大小之和。注意遍历过程中要跳过父节点，避免重复访问。
• 步骤3：遍历所有分割情况，找最小值
  遍历每个非根节点，它对应的分割后两个子树大小是size和N-size，计算两者的最大值，然后记录所有这些最大值中的最小值，这就是我们要的答案。

代码示例（Python） #

def find_balanced_cut(n, edges):
    # 构建邻接表
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    min_max = float('inf')
    subtree_size = [0] * n
    
    def dfs(node, parent):
        nonlocal min_max
        subtree_size[node] = 1
        for neighbor in adj[node]:
            if neighbor != parent:
                dfs(neighbor, node)
                subtree_size[node] += subtree_size[neighbor]
                # 计算当前边分割后的最大子树大小
                current_max = max(subtree_size[neighbor], n - subtree_size[neighbor])
                if current_max < min_max:
                    min_max = current_max
    
    dfs(0, -1)
    return min_max

# 测试用例：n=5，边为[[0,1],[0,2],[1,3],[1,4]]
# 最优分割是砍掉0-1，分成3和2的子树，max值为3，函数返回3

算法效率说明 #

整个算法只需要一次DFS遍历（O(N)时间）加上一次结果计算遍历（O(N)时间），总时间复杂度为O(N)，空间复杂度主要来自邻接表和递归栈（最坏链状树时递归栈为O(N)，也可以改成迭代DFS避免栈溢出）。

补充细节 #

• 如果N是偶数，最优情况是找到能分成两个N/2大小子树的边（如果存在）；如果是奇数，最优结果必然是分成floor(N/2)和ceil(N/2)，此时最小值就是ceil(N/2)。
• 要是需要找到具体是哪条边，只需要在计算current_max时同步记录对应的边即可。

内容的提问来源于stack exchange，提问作者Rabie