Kernighan-Lin算法
Kernighan-Lin算法
提问于 2013-07-08 17:51:35
有人知道这个算法吗，因为我正在考虑使用它，但我不确定它是否真的满足我的所有要求。所以基本上，我想要做的是将一个图分成几个子图。然而，每个子图的节点应该是连接的，也就是说，不应该是这样的情况，例如，如果我想到达节点x，我必须通过另一个子图。而这正是我所关心的。有没有可能，当我用Kernighan-Lin算法分割一个图时，子图的节点会分散在各处？
回答 1
Stack Overflow用户
发布于 2013-07-08 20:05:42
是的，K-L可以创建不连通的子图。例如，它将8个顶点的星形分开
* * *
\|/
*-*-*
/|
* *分成两个四顶点子图，其中一个不含中心的子图必然不连通。我不知道您希望在这个示例中发生什么。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17523691
复制相关文章
相似问题
腾讯云开发者
