寻找最小顶点连通子图
Find Minimum Vertex Connected Sub-graph
首先，我不得不承认我不擅长图论
我有一个弱连通的有向图 G=(V,E)，其中 V 大约有 1600 万，E 大约有 1.8 亿。
对于给定的集合S，它是V的一个子集（S的大小将在30左右），是否可以找到一个弱连通的子图G'=(V',E') 其中 S 是 V' 的子集，但尽量保持 V' 和 E' 的数量尽可能小？
图G可能会改变，我希望有一种方法可以实时找到子图。 （当进程写入G时，G会被锁定，所以不用担心G在你的子图计算还在运行时被改变。）
我目前的解决方案是为S中的每对顶点找到最短路径，并合并这些路径以获得子图。结果还可以，但是 运行 时间非常昂贵。
有没有更好的方法解决这个问题？
如果您对当前方法的结果感到满意，那么至少可以做得更快：
将 S 中的每个顶点分配给不相交集合数据结构中的集合：https://en.wikipedia.org/wiki/Disjoint-set_data_structure。那么：
- 对图进行广度优先搜索，从 S 作为根集开始。
- 当您搜索发现一个新顶点时，记住它的前导并将它分配到与其前导相同的集合。
- 当您发现连接两个集合的边时，合并集合并按照前导链接将连接路径添加到 G'
考虑做完全相同的事情的另一种方式：
- 根据与 S 的距离对 E 中的所有边进行排序。您可以为此使用 BFS 发现顺序
- 使用 Kruskal 算法为 G 生成生成树，按该顺序处理边 (https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)
- 在 S 中选择一个根，并删除所有不包含 S 成员的子树。完成后，每个叶子都会在 S 中。
这不一定会找到可能的最小子图，但会最小化它与 S 的最大距离。
首先，我不得不承认我不擅长图论
我有一个弱连通的有向图 G=(V,E)，其中 V 大约有 1600 万，E 大约有 1.8 亿。
对于给定的集合S，它是V的一个子集（S的大小将在30左右），是否可以找到一个弱连通的子图G'=(V',E') 其中 S 是 V' 的子集，但尽量保持 V' 和 E' 的数量尽可能小？
图G可能会改变，我希望有一种方法可以实时找到子图。 （当进程写入G时，G会被锁定，所以不用担心G在你的子图计算还在运行时被改变。）
我目前的解决方案是为S中的每对顶点找到最短路径，并合并这些路径以获得子图。结果还可以，但是 运行 时间非常昂贵。
有没有更好的方法解决这个问题？
如果您对当前方法的结果感到满意，那么至少可以做得更快：
将 S 中的每个顶点分配给不相交集合数据结构中的集合：https://en.wikipedia.org/wiki/Disjoint-set_data_structure。那么：
- 对图进行广度优先搜索，从 S 作为根集开始。
- 当您搜索发现一个新顶点时，记住它的前导并将它分配到与其前导相同的集合。
- 当您发现连接两个集合的边时，合并集合并按照前导链接将连接路径添加到 G'
考虑做完全相同的事情的另一种方式：
- 根据与 S 的距离对 E 中的所有边进行排序。您可以为此使用 BFS 发现顺序
- 使用 Kruskal 算法为 G 生成生成树，按该顺序处理边 (https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)
- 在 S 中选择一个根，并删除所有不包含 S 成员的子树。完成后，每个叶子都会在 S 中。
这不一定会找到可能的最小子图，但会最小化它与 S 的最大距离。