如何高效移除图中无法从指定顶点集到达的顶点

咱们先明确下，这个问题和以下两个 clique（也就是团）相关的问题完全不重复：

• 如何移除图中无法被团覆盖的顶点？
• 如何移除图中顶点同时保留特定顶点的团覆盖？

咱们这个问题的核心是：移除那些无法从指定顶点集到达的顶点，和顶点是否属于团没有任何关系。

问题场景与常规解法 #

举个玩具例子：假设图里有一些标记为"x"的顶点，我们要移除所有从这些"x"顶点出发都走不到的顶点（就像例子里的橙色顶点）。

常规的做法是：对每个标记"x"的顶点单独做深度优先搜索（DFS），记录所有被访问到的顶点，最后把不在这个访问集合里的顶点从图中移除。但这种方法在图很大的时候，效率会比较低——毕竟如果有k个"x"顶点，相当于要做k次遍历，很容易重复访问已经遍历过的节点。

更高效的优化方案 #

其实咱们可以把所有标记"x"的顶点作为起始源点，一次性启动遍历（多源BFS或者多源DFS），这样只需要遍历一次可达区域，就能拿到所有需要保留的顶点：

1. 初始化一个访问状态集合（比如用布尔数组或者哈希集合，大图里布尔数组效率更高），把所有标记"x"的顶点都标记为已访问，同时把它们加入遍历队列（BFS用队列，DFS用栈）。
2. 开始遍历：每次从队列/栈里取出一个顶点，遍历它的所有邻接顶点，如果邻接顶点还没被访问过，就标记为已访问并加入队列/栈。
3. 遍历结束后，所有未被标记为已访问的顶点，就是需要移除的顶点。

这种方法的时间复杂度是O(V+E)（V是顶点数，E是边数），和单次遍历的复杂度一样，比逐个遍历k次的O(k*(V+E))高效太多，尤其是当k很大的时候，能节省大量时间。

如果是有向图的话，还要注意是要找正向可达（从指定顶点出发能走到的）还是反向可达（能走到指定顶点的），调整遍历方向就行，但核心思路还是多源遍历。

总结 #

相比逐个对指定顶点做DFS，多源遍历（BFS/DFS）是更高效的解决方案，能避免重复遍历，大幅提升大图场景下的处理速度。

备注：内容来源于stack exchange，提问作者thunderbird30