基于边权的无向图节点二分划分算法需求及相关资源咨询

你需要的是将无向图节点划分为大小完全相等的两个子集，并最小化同组内所有边的权值总和——这本质是平衡图划分问题的典型场景，同时等价于最大化跨组边权总和（因为图的总边权固定，同组边权和越小，跨组边权和越大）。以下是可直接复用的经典算法和自研参考方向：

经典算法选择 #

1. Kernighan-Lin算法 #

这是专门针对平衡图划分的启发式算法，完全适配你的需求：

• 流程：先生成满足大小约束的初始划分，然后迭代计算两个子集内节点交换后的收益（同组边权的减少量），选择收益最大的节点对交换，直到无法优化为止。
• 适配性：对于你给出的4节点示例，即使初始划分是AB-CD（同组边权和为4），算法也会快速找到交换B和C的最优方案，得到AC-BD的划分（同组边权和为3）。
• 适用场景：中小规模图，实现简单，收敛快。

2. 谱划分算法 #

适合处理大规模图的近似最优划分：

• 核心逻辑：通过计算图的拉普拉斯矩阵的第二小特征向量（Fiedler向量），根据向量分量将节点分组，再调整分组以满足大小约束。
• 优势：能给出全局近似最优解，后续可结合Kernighan-Lin算法做局部优化，进一步提升划分质量。

3. Metis算法 #

工业级图划分工具，支持严格的大小约束：

• 采用多层级划分策略：先粗化图（合并节点缩小规模），在粗化图上做初始划分，再逐步细化并结合Kernighan-Lin优化。
• 适用场景：百万级节点的大规模图，划分效率和质量都有保障。

自研参考方向 #

由于该问题属于NP难问题，不存在多项式时间的精确解法，自研时可以：

• 基于Kernighan-Lin算法优化初始划分策略：比如优先将高边权连接的节点分到不同组，减少迭代次数。
• 结合谱划分的全局特性与贪心策略：先通过谱划分得到近似分组，再用贪心调整满足大小约束并优化目标。
• 针对特定边权分布场景设计定制化规则：比如边权集中在少数节点时，优先处理这些节点的划分。

示例验证补充 #

你给出的示例中，所有等大小划分的同组边权和计算如下：

AB CD = 3 + 1 = 4
BC AD = 1 + 3 = 4
AC BD = 2 + 1 = 3

最优划分AC-BD正是通过最小化同组边权和得到的，上述算法都能自动找到该结果。

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