algorithm - 子图算法

Question

我想知道是否存在一种有效的算法 S = F(v,G) 从 DAG G = (V,E) 构造子图 S，使得 S 中的所有路径都包含的顶点 v V. 如果是这样，就可以有效地将 F 扩展到一组顶点 N 的 F'(N,G)。我对任何用于最初存储 DAG G 的数据结构持开放态度。

实际上我忘记添加的一个条件是 G 有一个没有入边的唯一顶点 r 并且路径必须是 d 是没有出边的顶点的形式。

我错过的另一个条件是给定扩展的 F'(N,G) 这样对于 N 的所有 v,w 如果 < r,..,v,..,w > 其中 w 是一个汇，那么我们应该忽略路径 < r,..,v,..,x > where x != w.

我实际上有一个解决方案，但当#V > 2000 且#N > 2 时，它无法扩展。

Answer 1

我假设您正在寻找 G = ( {r} + V + {d}, E ) 的最大子图 S，其中 r 是唯一的源节点，d 是汇点，使得从 r 到 d 的每条路径传递一个特定的节点 v。

我提出的算法:

1. 找到 r 和 v 之间的所有路径，例如使用Find the paths between two given nodes? 中提供的答案

2. 使用相同的算法找到 v 和 v 之间的所有路径。由于 G 是非循环的，因此从 v 到 d 的任何路径都不能返回到已在步骤 1 中找到的路径。因此，在生成的图中，r 和 d 之间的所有路径都将通过 v。