Kernighan-Lin算法

Question

有人有点了解此算法，因为我正在考虑使用它，但是我不确定它是否真的满足我的所有要求。因此，基本上，我想做的是将一个图分成几个子图。但是，每个子图的节点都应该连接，也就是说，如果要到达节点x，则不必经过另一个子图。这正是我的关注。当我使用Kernighan-Lin算法拆分图时，子图的节点最终会散落到各处吗？

Answer 1

是的，KL可能会创建断开的子图。例如，它分割了8个顶点的星]

* * *
 \|/
*-*-*
 /|
* *

分为两个4个顶点子图，其中一个（其中一个不包含中心）不一定是相连的。我不知道您希望在此示例中发生什么。