拆解图算法
拆解图算法
提问于 2017-03-16 15:06:50
图有n个顶点和m个边。图开始连接，然后按照它们在列表中出现的顺序删除边缘。在处理结束时，图被断开。
因此，在边的列表中有一个特定的边，在删除它之前，有一个连通分量，它的顶点数超过n/4的地板。去除该边后，图中不存在大于n/4顶点的顶点的连通分量。
我将如何设计出最好的算法来找到这个边缘。我是否只是开始删除边缘，然后每次遍历图表，以检查最大的连接组件是否足够？这是在O(nm)时间，但我觉得必须有更快的方法。我认为答案与使用不连接的集合来查找连接的组件有关，但我不确定如何实现它。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-03-16 18:33:40
考虑反向运行此过程，添加边而不是删除边。该过程与Kruskal的算法有很大的相似之处(每个节点都是自己启动的，并且在连接不同连接的组件中添加了边)，但只要至少有一个连接组件，其中至少包含⌊n/4⌋节点，就会停止。
解决这一问题的一种方法是使用Kruskal算法的一个改进版本和一个联合查找数据结构，以使联合中的每个代表都能在其连接的组件中存储节点数。以反向顺序遍历边缘，如果端点已经连接并以其他方式将其连接起来，则在每一点丢弃边缘。如果您添加了一个边缘，导致至少有一个⌊n/4⌋节点的连接组件，那么您已经找到了要寻找的边缘。如果使用联合查找数据结构的快速实现，这将在时间O(n + mα(n))中运行，这在实践中基本上是线性的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42837833
复制相关文章
相似问题
腾讯云开发者
