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

问题背景 #

给定无向图和一个顶点集（顶点集内顶点未必连通），需移除所有无法从该顶点集到达的顶点。当前采用多起点DFS（从每个标记顶点出发遍历、记录访问顶点，再移除未访问顶点）的方案，但处理大型图时效率偏低，寻求更高效的实现方式。

优化实现方案 #

以下是针对大图场景的高效优化思路：

• 替换为多起点BFS遍历
  相比DFS，BFS在大图场景下更具优势：递归DFS易触发栈溢出，迭代DFS的栈操作缓存命中率低；而BFS基于队列的层序遍历更契合现代CPU的缓存机制，能减少内存访问开销。实现时直接将所有指定顶点一次性加入队列，批量处理，避免多次单独启动DFS的额外损耗。

• 优化图的存储结构
  若当前使用邻接矩阵，建议切换为邻接表（如数组+动态数组实现），邻接表的遍历时间复杂度为O(V+E)，远优于邻接矩阵的O(V²)。对于超大型图，可进一步采用**压缩稀疏行（CSR）**格式存储，提升内存利用率与遍历速度。

• 并行化遍历（多核环境）
  将指定顶点集拆分为多个子集，分配给不同线程同时执行BFS/DFS，最后合并所有访问标记。需使用线程安全的标记容器（如原子布尔数组）避免竞态条件，充分利用多核算力缩短处理时间。

• 遍历过程剪枝
  遍历中若已标记全部顶点，可直接终止流程；每次访问邻接顶点时先检查标记状态，跳过已访问顶点，减少无效操作。

• 使用位图存储访问标记
  用位图（如BitSet、std::bitset或自定义位数组）替代普通布尔数组存储访问状态，大幅降低内存占用。内存占用减少会降低缓存 miss 概率，显著提升遍历速度，尤其适用于顶点数量极大的图。

示例说明 #

示例图中带“x”标记的顶点为起点集，橙色顶点是无法从起点集到达的顶点，通过上述方案可高效筛选并移除这些橙色顶点，仅保留所有可达顶点构成的子图。

内容的提问来源于stack exchange，提问作者thunderbird30