algorithm - 如何连接拓扑排序的 DAG 中的节点，以便每个上游节点最多可以到达任何下游节点 2 跳？

Question

我正在尝试解决这个问题：给定 n 个节点，我需要插入边以形成拓扑排序的 DAG 类型的情况。每个节点应该能够通过 1 跳或 2 跳路径（不再）到达任何下游节点。我最多使用 theta(nlogn) 边缘来做到这一点。我该怎么做？

n=3 的示例：

给定的线索是使用分而治之。如果有n个节点，如果我们假设前半部分的n/2已经有这个属性，最后n/2也有这个属性，那么如何将这两部分结合起来，让n个节点有这个属性？属性是如果 i 和 j 都属于同一半，我们最多可以在 2 跳内从 i 到 j。展示如何添加 theta(n) 附加边，以便如果 i 在前半而 j 在后半部分我们可以只使用两条边从 i 到 j。

我该怎么做？我尝试将前半部分的叶子连接到下半部分的每个节点，然后对叶子的祖父母做同样的事情，依此类推。但这使用 (n/4)*n，它是二次的。

标签： algorithmcomplexity-theorydirected-acyclic-graphsdivide-and-conquertopological-sort

Answer 1

一个简单的解决方案是从前半部分获取汇节点（一个具有 0 个出边的节点，如果使用这种方法构建 DAG 则应该只有一个），并从那里向所有节点添加一条有向边。下半场。这相当于添加 n/2 条边。然后，取出这个汇节点的所有祖先（前半部分的所有其他节点）并从它们添加一条边到汇节点。这将是另一个 (n/2)-1 个边，总计为线性数量的附加边。

从归纳假设来看，后半部分以及前半部分已经具有 2 跳属性。前半部分的所有节点也将与后半部分的每个节点相距 2 跳。这条路径将从任何前半节点到原始汇节点，然后再到后半节点的任何节点。我们现在有一个新的 DAG，它结合了 2 个 DAG，保留了 2 跳属性，并且有一个单汇节点。

该算法的分析类似于归并排序。我们将问题拆分为 2 个递归子问题，并有一个线性步骤组合结果。这形成了与合并排序相同的递归关系，并为我们提供了整体的 nlogn 复杂性。