如何在有向无环图中删除无效的边？

Question

如何在有向无环图中删除无效的边？

algorithmgraph-theorydirected-acyclic-graphs

5

以下图表示例是有向无环图的一部分，需要进行分层和清理，以便仅保留连接连续层的边缘。

因此，我需要消除形成“快捷方式”的边缘，即跳跃非连续层之间的边缘。

以下考虑事项适用：

蓝色环层是有效的，因为从83140开始到29518结束时，两个分支都有相同数量（3个）的中间节点，并且没有更长的路径连接起始和结束节点；
绿色环层从94347开始到107263结束，有一个无效边（已经被红色叉掉），因为左侧分支仅包含一个中间节点，而右侧分支包含三个中间节点；此外，由于该分支的第一条边已经是有效的 - 我们知道它属于有效的蓝色环层 - 因此可以知道哪个是正确的边要划掉 - 否则将无法确定应将哪个层分配给节点94030，因此应将其删除；
如果我们在考虑绿色环层之后再考虑粉色环层，则知道应该删除下面的红色交叉边。
但是，如果我们仅考虑黄色环层，则两个分支似乎都是正确的（它们包含相同数量的内部节点），但实际上它们只是看起来正确，因为它们包含对称错误（快捷方式跳过相同数量的节点）。如果我们局部考虑这个环层，至少一个分支将以错误的层结束，因此需要使用更全局的数据来避免此错误。

我的问题如下：

在制定和可能解决这个问题时涉及了哪些典型的概念和操作？
是否有相关算法？

- heltonbiker

你所尝试的是接近于传递闭包缩减：https://en.wikipedia.org/wiki/Transitive_reduction ...但并不完全相同。你确定你真的不想要一个传递闭包缩减吗？ - Matt Timmermans

@MattTimmermans 是的，我非常确定。具体来说，在图中被划掉的边缘（用红色X标记）不应该出现在图中，但如果使用传递闭包缩减，则会保留这些边缘。它们不应该出现在图中，因为这将意味着节点之间存在连接，而实际上它们并没有连接（此图是通过图像处理生成的，这些快捷方式是由原始图像中的伪影导致的）。 - heltonbiker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shihab Shahriar Khan · Accepted Answer

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

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

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

如果 depth[p]+1 < depth[c]，那么意味着c有一个比p深的父节点。所以p到c的边必须是一个shortcut。
如果 depth[p]+1 > depth[c] 并且 depth[c]!=-1，那么意味着c有一个比p浅的父节点。所以p是一个更好的父节点，并且c的另一个父节点必须与p有一个shortcut。

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

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

由于图可以有多个根，我们应该有一个变量来标记已访问的节点，并重复上述步骤以处理任何未被访问的节点。

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

（注意：我们可以通过一次遍历来实现这一点。不需要标记有问题的节点，我们可以为所有节点维护一个“parent”变量，并在发生情况2时删除旧父边缘。情况1应该很明显）