子图算法

Question

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

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

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

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

Answer 1

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

我提出的算法：

例如，使用Find the paths between two given nodes?

• Find

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

Answer 2

结果图包含从v可达的节点和从v可达的节点v(或转置的子图中从v可达的节点)。获取可达节点集可以高效地完成。

对于一组节点，这可能很容易扩展:您只需在广度优先搜索的开始添加所有这些节点。