查找最小顶点连通子图

Question

首先，我必须承认我不擅长图论。

我有一个弱连接的有向图G=(V,E)，其中V约为1600万，而E约为1.8亿。

对于给定集合S，它是V的子集（S的大小约为30），是否有可能找到弱连接的子图G'=(V',E')，其中S是V'的子集，但尝试保持V'和E'的数量尽可能小？

我当前的解决方案是在S中找到每对顶点的最短路径，并将这些路径合并以获得子图。结果还可以，但是运行时间非常昂贵。

是否有更好的方法来解决此问题？

Answer 1

如果您对当前方法的结果感到满意，那么至少可以更快地完成它：

将S中的每个顶点分配给不连续集合数据结构中的集合：https://en.wikipedia.org/wiki/Disjoint-set_data_structure。然后：

• 以S为根集，进行图的广度优先搜索。
• [当搜索发现新顶点时，请记住其先前节点，并将其分配给与先前节点相同的集合。
• [当您发现连接两个集合的边时，合并集合并遵循先前的链接将连接路径添加到G'

另一种考虑做完全相同的事情的方式：

1. 根据E中的所有边缘与S的距离对其进行排序。您可以为此使用BFS发现顺序
2. 使用Kruskal算法为G生成生成树，以该顺序处理边缘（https://en.wikipedia.org/wiki/Kruskal%27s_algorithm]
3. 在S中选择一个根，并删除所有不包含S成员的子树。完成后，每个叶子都将在S中。