图解算法
一个图有n个顶点和m个边。 图形开始连接，然后按照它们出现在列表中的顺序删除边线。 在这个过程结束时，图形被断开。
因此，在边缘列表中存在特定的边缘，使得在去除边缘之前，有一个连接的分量超过n / 4个顶点的顶点。 删除该边后，图中没有超过n / 4个顶点的连通分量。
我将如何去设计最佳算法来找到这个边缘。 我是否刚刚开始删除边，然后每次遍历图来检查最大连接组件是否满足要求？ 这在O（nm）时间运行，但我觉得必须有一些更快的方式。 我认为答案与使用不连贯的集合来查找连接的组件有关，但我不确定如何去实现它。
考虑反向运行此过程，添加边而不是删除边。 该过程与克鲁斯卡尔算法非常相似（每个节点由其自身开始，并且在连接不同的连接组件时添加边），除非一旦至少有一个连接组件至少有⌊n/4⌋节点。
解决此问题的一种方法是使用Kruskal算法的修改版本和增强的联合查找数据结构，以便联合查找结构中的每个代表存储其连接组件中的节点数。 以相反的顺序遍历边，如果端点已经连接，则在每个点放弃边，否则将它们链接起来。 如果添加一个导致存在至少⌊n/4⌋节点的连接组件的边缘，则您已找到要查找的边缘。 如果使用union-find数据结构的快速实现，这将在时间O（n +mα（n））中运行，这在实践中基本上是线性的。
链接地址: http://www.djcxy.com/p/70669.html上一篇: Graph Algorithm for Dismantling
下一篇: Removing minimum no of edges to disconnect two vertices in a graph