我正在寻找一种有效的算法来发现删除图中的一组节点是否会将图拆分为多个组件。
形式上，给定无向图G=(V，E(和顶点的非空集W⊆V，返回trueiffW为顶点割集。图中没有边权重。
到目前为止，我脑海中出现的是使用不相交集：
- 用W中节点的所有邻居初始化不相交集，其中每个集都包含一个这样的邻居
- 在V\W的所有节点的广度优先遍历期间，对于每个新探索的节点X，正好有以下情况之一成立：
- X已经与其前代在同一集合中
- X在不相交集中不存在⇒被添加到与其前一个组件相同的集合中(这两种情况都意味着正在进一步探索连接的组件(
- X在不同的集合中⇒合并不相交的集合(到目前为止，两个组件看起来是不连接的，但事实证明是连接的(
- 只要不相交的集合只包含一个集合(甚至在遍历完成之前(，结果就是
false - 若遍历完成时，不相交的集合包含2个或多个集合，则结果为
true
时间复杂度为O(|V|+|E|((假设不相交集的时间复杂度是 O(1(你知道更好的解决方案吗(或者在提议的解决方案中看到任何缺陷(？ 注意：由于它经常出现在谷歌搜索结果中，我想明确指出，我并不是在寻找算法来找到迄今为止未知的顶点割集，更不用说最优了。给出了顶点集，任务只是说是或否。 注2：此外，我不搜索边割集验证(我知道在图中查找割集，但无法为顶点想出类似的解决方案(。 谢谢！ 更新：我发现，在 背后的实际案例是电信网络中断。当某个节点发生故障，导致整个网络断开连接时，一个组件(包含与更高级别网络连接的节点(仍然正常，需要报告其他所有组件。true结果的情况下，我还需要层次结构中断开组件中节点的数据，这取决于与移除节点的距离。因此选择了BFS。我为后期编辑道歉。
有一个unordered_set<int> r来存储要删除的顶点集。
正常运行DFS，但仅转到不在r中的相邻项。如果您总是访问未访问的节点，请在访问的节点数上加1。
如果最终访问节点的数量小于|V| - r，则该集合对图进行划分。
使用这种方法，您不需要在图中进行更改，只需忽略r中的节点，您可以使用unordered_set<int>在O(1(中检查这些节点。
复杂性与普通DFS相同。
难道不能通过对图执行深度优先搜索来获得O(|V|(复杂性吗？从V中删除集合W并执行DFS。记录已处理的节点数，并在无法访问更多节点时停止。如果处理的节点数小于|V|-|W|，则W是割集。