在无向图中计数大小为k的连通组件
在无向图中计数大小为k的连通组件
提问于 2020-06-01 15:08:05
给定一个大小为n的无向图。如何计算图中有多少个大小为k的连接组件？假设为k<=n，并且输入图是连接的。
例如，给定一个[(0,1), (1,2)]的图。它具有3大小为1的连接组件、2大小为2的连接组件和1大小为3的连接组件。
回答 2
Stack Overflow用户
发布于 2020-06-01 20:50:13
我认为你的问题在here中也是一样的(这是关于寻找所有大小为k的连通子图，时间复杂度是n^ k)。
Stack Overflow用户
发布于 2020-11-15 10:43:15
如果你仍然感兴趣，你的问题在O(n*(d-1)^k)中是可解的，d表示图的度，方法是选择一个节点N，然后迭代地从它的邻居添加节点，直到达到k个节点。
如果效率对你来说是个问题，this paper提出了另一个算法来解决你的问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62127228
复制相关文章
相似问题
腾讯云开发者
