0

有没有一种有效的方法来删除不属于 DAG 中两个节点之间最长路径的所有边？例如，对于图（DAG）： (1->2, 2->3, 2->4, 1->3, 1->4) 我想删除边 1->3, 1-> 4 因为路径 1->2->3, 1->2->4 更长

编辑：所以我认为最好的方法是使用拓扑排序并从右到左遍历数组，同时为每个节点聚合其后代。然后对于每个边 a->b，我们可以使用 a 的所有其他直接后代检查 b 是否可以从 a 到达（如果是，我们删除边）。但我没有找到一个实现，我不确定它是否正确，有没有人知道这样的实现？

4

1 回答 1

0

您建议的算法是正确的，因为如果一条边在任何最长的路径上，那么它必须是从其源到目标顶点的最长且唯一的路径。因此，您可以删除任何多余的边缘。

您尝试做的事情的名称是“传递减少”：https ://en.wikipedia.org/wiki/Transitive_reduction

虽然您的算法有效，但我认为拓扑排序对您没有任何好处。简单的算法是从每个顶点进行搜索以找到到达其相邻顶点的其他方法。

于 2021-01-18T14:16:04.187 回答