首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >增量求约简图中不交集合的个数

问增量求约简图中不交集合的个数
EN

Stack Overflow用户
提问于 2014-06-20 16:32:12
回答 1查看 81关注 0票数 1

我找出图G中不相交集合的数量,然后删除图G的一些顶点,生成图G',我想找出G'中不相交集合的数量,有没有什么好的算法可以做到这一点,而不用像对G一样对G'做同样的事情

EN

回答 1

Stack Overflow用户

发布于 2014-06-20 16:42:14

我建议您按相反的顺序执行此操作。

我的意思是:

  1. 从最小的图G‘开始,使用并集查找算法查找不相交的集。
  2. 然后在G中添加新元素,并通过继续使用从步骤1的输出开始的并集查找算法将一些其他集连接在一起。
  3. 根据需要重复添加新折点和查找不相交集的次数

相反顺序更好的原因是因为您只需要访问步骤2中的新顶点,因此您最终不会为每个新图重复大量工作。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/24323067

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档