algorithm - 在简化图中逐步查找不相交集的数量

Question

我在图中找到不相交集的数量，G然后删除图的一些顶点G并制作图G'，我想在其中找到不相交集的数量G'，是否有任何好的算法不做与G'我们一样的事情到G？

Answer 1

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

我的意思是：

1. 从最小的图 G' 开始，并使用联合查找算法来查找不相交的集合。
2. 然后在 G 中添加新元素，并通过从步骤 1 的输出开始继续使用并集查找算法将一些额外的集合连接在一起。
3. 重复添加新顶点并根据需要多次查找不相交的集合

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