用于收集两个节点之间任何路径上的所有边的图算法

Question

我需要找到有向图中两个节点 [src, dest] 之间的任何路径上的所有边。

表示每条边（从base到head）必须满足：

有一条从 src 到 base 的路径
有一条从头到尾的路

我可以收集所有连接到 src 的边，收集所有反向连接到 dest 的边，并计算它们的交集。

但是总得有个算法吧？（不知道有没有更高效的）所以我正在搜索名称，或者用现有算法解决它的巧妙解决方案。

Answer 1

如果您只回答一次问题，那么对您的问题发表评论的人是正确的：您提出的解决方案是正确且快速的。但是，如果您在固定图表中针对不同的 src 和 dest 多次回答您的问题，则有一种方法可以 "index" 信息来加快查询速度。

Tarjan's algorithm 将在 O(V+E) 时间内将有向图分解为强连通分量 (SCC)。强连通分量是一组顶点，它们都可以通过有向图相互到达。

这组强连通分量本身将形成一个有向无环图 (DAG)。

如果src和dest在同一个SCC中，那么你要找的边集就是SCC中的边集。

如果DAG中包含dest的SCC无法从包含src的SCC到达，则没有从src到dest的路径，所以你要找的边集是空的。

如果包含dest的SCC从包含src的SCC可达，则需要在DAG中找到从src SCC到dest SCC的所有路径，这是一个非常简单的动态规划问题。那么你要的边集就是src SCC和dest SCC之间的所有SCC中的边集，加上DAG中相关路径的边到原图中边的"pullbacks"。

这听起来可能令人困惑，但维基百科页面上的图表可能有助于澄清。

Answer 2

为了获得总体结果，我将报告我所做的事情。

我实现了题中提到的算法。（我们称它为 thigg 的算法，因为没有人提到名字）

蒂格算法：

for each node in the graph:
     if there is a path from src to this node 
        and a path from this node to dest, 
       push node to the result list.

正如 Edward Doolittle 在他的中提到的那样，之前可以通过识别强连接组件并将它们减少到一个节点来优化图形。这将减少算法在每个运行.

上的工作量

我使用 Boost-Graph-Library（没有 SCC 优化）实现了 thiggs 算法，其中 a 是源顶点，b 是目标顶点：

我使用广度优先搜索来获取 a:

可到达的所有顶点的列表

boost::breadth_first_search(graph, a, visitor(vis));

其中 vis 是一个自定义访问者，它将所有访问过的顶点放入一个列表中。然后它恢复图形以获得所有可以到达 b

的顶点

boost::breadth_first_search(boost::make_reverse_graph(graph), b, visitor(vis));

最后计算交集：

std::set_intersection(froma.begin(),froma.end(),fromb.begin(),fromb.end(),back_inserter(inters));

您的图形必须是双向的才能使用 make_reverse_graph。

该算法也适用于问题中提到的边。

用于收集两个节点之间任何路径上的所有边的图算法

Graph algorithm to collect all edges which are on any path between two nodes

algorithm

graph

graph-algorithm