如何删除渐变定向acyclig图中的无效边？

Question

下面的图表示例是有向无环图的一部分,该图将被分层和清理,以便仅保留连接连续层的边.

所以我需要的是消除形成"快捷方式"的边缘,即在非连续层之间跳转.

以下注意事项适用:

1. 蓝色环分层是有效的,因为从83140开始到29518结束,两个分支具有相同数量(3)的中间节点,并且在起始节点和结束节点之间没有更长的路径;
2. 绿色环从94347开始到107263结束,具有无效边缘(已经红叉),因为左分支仅包含一个中间节点,而右分支包含三个中间节点; 此外,由于该分支的第一个边缘已经有效 - 我们知道它与有效的蓝色环相关 - 可以知道哪个是交叉输出的右边缘 - 否则就不可能知道应该分配哪个层到节点94030,所以它应该被删除;
3. 如果我们在考虑绿色环之后考虑粉色环,我们知道要去除下部红色交叉边缘.
4. 但是如果我们只考虑黄色环,两个分支看起来都是正确的(它们包含相同数量的内部节点),但实际上它们看似正确,因为它们包含对称错误(快捷方式在两个分支上跳过相同数量的节点).如果我们在本地获取此环,则至少有一个分支最终会出现错误的层,因此有必要使用更多的全局数据来避免此错误.

我的问题是:

1. 制定中涉及哪些典型的概念和操作以及该问题的可能解决方案？
2. 有算法吗？

Answer 1

首先，对图进行拓扑排序。

现在从排序数组的开头开始，开始广度优先搜索并尝试找到每个节点的正确“深度”（即距根的距离）。由于一个节点可以有多个父节点，因此对于一个节点x，depth[x]是其所有父节点的最大深度加一。我们depth将所有节点初始化为-1。

现在在 bfs 遍历中，当我们遇到一个节点 时p，我们尝试更新它的所有子节点的深度c，其中depth[c] = max(depth[c],depth[p]+1)。现在我们有两种方法可以通过快捷方式检测孩子。

• 如果depth[p]+1 < depth[c]，则意味着c有一个深度比 更高的父级p。所以edge p to c一定是一条捷径。
• 如果depth[p]+1 > depth[c]和depth[c]!=-1，则意味着c有一个深度低于 的父级p。更好的p父级也是如此，并且 的另一个父级必须有 的快捷方式。cp

在这两种情况下，我们都将其标记c为有问题。

现在我们的目标是对于每个“有问题”的节点x，我们检查它的所有父节点，其深度应该为depth[x]-1。如果其中任何一个的深度低于该值，则该一个有一个快捷边，x需要将其删除。

由于图可以有多个根，因此我们应该有一个变量来标记visited节点，并对任何未访问的节点重复上述操作。

这将解决黄环问题，因为在我们访问任何节点之前，它的所有前辈都已被访问并正确排序。这是通过拓扑排序来保证的。

（注意：我们只需一次即可完成此操作。我们可以为parent所有节点维护一个变量，而不是标记有问题的节点，并在情况 2 发生时删除旧父节点的边。情况 1 应该是显而易见的）