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

Question

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

意味着每条边(从基到头)都必须满足:

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

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

但必须有一个算法，对吗？ (不知道有没有效率更高的)所以我正在搜索名称，或者用现有算法解决它的巧妙解决方案。

Answer 1

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

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中相关路径的边到原始图中边的“回拉”。

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