在有向图中有效搜索

Question

我有一个有针对数百万个顶点和边缘的图形。给出了一组顶点，假设它们称为“ start_points”。还给出了另一组称为“ end_points”的顶点。问题是找到可以从哪些start_point到达哪些end_points。

这是一个示例：

START_POINTS: S1 S2 S3 S4 S5 S6 S7 ... 
END_POINTS  : E1 E2 E3 E4 E5 E6 E7 ... 

该算法应能够告诉以下内容：

S1 can reach to E1, E2, E6
S2 can reach to E9, E10
S3 cannot reach any END_POINT
S4 can reach to .....
....

可能无法从任何start_point到达某些end_point。

现在，问题是：实施它的最有效方法是什么？

我尝试从每个start_point一对一开始，并使用深度优先搜索（或BFS，它确实会大大改变运行时）。但是，这需要很多时间，因为有很多start_point（也有很多end_points）。

可以优化搜索，因为start_point的追踪路径之间存在巨大的重叠。一个人需要记住哪些路径可以到达哪些end_points。完成此操作的最有效方法是什么？这可能是众所周知的问题，但我还找不到解决方案。

1月6日编辑：

我试图实现HighBandWidth的想法（以类似于Keith Randall提出的方式）：对于每个节点，如果此节点不是启动或终点，请将所有输入连接到输出，然后删除节点。

foreach NODE in NODES
    Skip if NODE is START_POINT or END_POINT
    foreach OUTPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
    end
    foreach INPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
        foreach OUTPUT_NODE of NODE
            Connect INPUT_NODE to OUTPUT_NODE
        end
    end
    Remove NODE from NODES
end

这开始非常快，很快变得非常缓慢，主要是因为剩余节点的输入/输出计数变得非常大，并且嵌套以杀死性能。知道如何使其更有效吗？

Answer 1

只需修剪图表即可摆脱所有没有出现在start节点或结束节点中的节点，然后用从其入站节点到出站目标的边缘代替它们。完成此操作后，请浏览所有其他节点（启动或结束节点），并将其从入站节点添加到其出站节点，而不会删除这些节点。在几个类似Djikstra的迭代中，您应该离开开始边缘。

Answer 2

这可能是过分的，但您可能想检查一下 Dijkstra. 。我过去在创建自己的虚拟节点路由表时使用过它。在这种情况下，您的所有节点的值为1，这意味着每个节点的成本都相同。

Answer 3

首先，运行 紧密连接的组件 算法。然后将所有连接的组件收缩到一个节点。然后执行一个 拓扑排序 图。然后，在单个通过中，您可以计算启动节点可以到达图中的每个节点（初始化每个启动节点s到集合{s}，然后按每个节点按拓扑顺序执行传入边缘的联合）。

您有一个潜在的问题，因为答案可能与＃start节点 *＃结束节点一样大，这可能很大。希望您有一些大型SCC可以收缩到单个节点，因为这可以使答案更加简洁（同一SCC中的所有启动节点都可以到达相同的位置，因此您只需要在集合中使用一个代表）。