在DAG中，如何找到路径收敛的顶点？

Question

我有一种有向无环图，但有一些约束。

1. 只有一个“入口”顶点
2. 可以有多个叶顶点
3. 一旦路径分割，该路径下的任何内容都无法到达另一路径（下面的一些示例会更清楚）
4. 可以有任意数量的“分割”顶点。它们可以嵌套。
5. “拆分”顶点可以拆分为任意数量的路径。下面的示例每个仅显示2条路径，但是可能更多。

我的挑战如下：对于每个“分裂”顶点（任何具有至少2个向外边缘的顶点），找到其路径重新连接的顶点-如果存在这样的顶点。该解决方案应尽可能高效。

示例A：

example a

在此示例中，顶点A为“拆分”顶点，而其“重新连接顶点”为F。

示例B：

example b

这里有两个分割的顶点：A和E。对于它们两个顶点，G都是重新连接顶点。

示例C：

example c

现在有三个分割的顶点：A，D和E。相应的重新连接顶点是：

• A-> K
• D-> K
• E-> J

示例D：

example d

[这里我们又有三个分割的顶点：A，D和E。但是这次，顶点E没有重新连接的顶点，因为其中一条路径提前终止。

Answer 1

听起来像您想要的是：

1. 将出度为0的每个顶点连接到单个终端顶点
2. 构造边缘反转图的dominator tree。链接的维基百科文章指出了执行此操作的几种算法。
3. “重新连接顶点”是其在边缘反转图中的直接控制者，即其在该控制者树中的父代。在原始图中，这称为其“后支配者”。如果这是您添加的终端顶点，则它在原始图形中没有重新连接的顶点。