考虑以下无向无环图:
如果我们将“根”定义为 A 和 E，是否有一种算法可以确定生成的有向无环图？:
我考虑过从根开始尝试某种 DFS 或 BFS，但我不太确定如何处理“等待”看看另一个根是否可能到达给定节点的需要。
最佳答案
我假设您正在寻找的是边缘的方向，使得
- 整体图是一个 DAG，并且
- DAG 的源节点是您指定的节点。
现在，我们忽略第二个约束。使整个图成为 DAG 的一个简单方法是将顺序 1 ... n 分配给节点，然后让边始终从较低节点指向较高节点。因此，问题是如何以提供第二个属性的方式分配数字。
我相信您可以通过在图表上运行 BFS 并使用所有 k 个根节点为队列播种来实现此目的。如果按照发现的顺序对节点进行编号，那么您将获得一个 DAG(节点的任何顺序都会给出一个 DAG)。此外，假设没有两个根彼此相邻，并且图的每个连通分量中至少有一个根，那么您的根将是唯一的根。
要看到这一点，假设没有一个根是相邻的并且图是连接的，然后为了矛盾起见假设其他节点是根。取除了您选择的也是根的节点之一之外编号最小的节点。因为节点被分配了一个编号，所以它一定是在 BFS 中发现的，因此它与也在 BFS 中发现的其他一些编号较低的节点相邻。但是，来自较低编号节点的边将有一个箭头指向较高编号的节点，因此它不会是根。
(如果您有两个相邻节点想要成为根，则无法实现此目的，因为一个节点将有一个箭头指向另一个节点。)
总的来说，它的运行时间为 O(m + n)，因为它只是图上的 BFS。
关于algorithm - 给定 "roots"从无向无环图创建有向无环图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61306032/