将图形划分为两个集群

Question

我有一个完整的加权图G(V, E)。我想将 V 划分为两个集群，以使集群内的最大边长最小化。解决这个问题最快的算法是什么？我相信这可以在 O(n^2) 时间内解决，其中 |V|=n。一种方法是使图形二分。我想不出完整的算法。谁能帮我找出完整的算法？

Answer 1

双色（深度优先搜索，O(n)时间）一个最大生成森林（Prim算法，O(n²)时间）。正确性证明留作练习。

郑重声明，对于只有 m 条边的稀疏图，我很确定有一个 O(m) 时间算法。