当有向图是线性时，按顺序返回节点。否则失败

Question

问题

我有一套 edges (a, b), ， 在哪里 a 和 b 是有向无环图 (DAG) 中的节点。

边的数量保证为节点的数量 - 1。

我正在寻找一种找到节点序列的算法 [n_1, ... n_n] 使得序列包含 全部 图中的节点，以及所有边 (n_i, n_i+1) 为了 0 < i < n 存在于 edges. 。如果该序列不可能，因为给定的一组 edges 不等于所需的边集，那么我需要抛出一个错误。

编辑：该图可能有任意数量的断开组件。我显然不认为具有多个断开组件的图是线性的。

到目前为止的想法

请注意，我正在检查的数量 edges 正是存在这样一个序列所需的边数。因此，当存在共享源或目的地的两条边时，该算法可能会失败。但是，我仍然需要得到该序列。

我意识到拓扑排序返回有向图的线性顺序，这满足了我的要求。但是，当图形不完全像那样线性时，我仍然希望失败，而不是无论如何都获得线性顺序。

也许我可以验证，然后进行拓扑排序。但这听起来效率很低。我也不确定这个问题中事物的正式名称，所以很难简单地查找算法。我觉得我在这里缺少一些简单的联系或技巧。

你能给我提供一个算法来完成这个任务吗？我将采用伪代码或您选择的任何语言。

Answer 1

我想出了一个至少通过我的测试用例的算法：

let N = set of all nodes
let E = set of all edges

if (|E| != |N|-1) fail

let possibleStartNodes = new set containing all of N
let nexts = new dictionary from node -> node

foreach (prev, next) in E:
  if (next not in possibleStartNodes) fail 
  remove next from possibleStartNodes
  nexts[prev] = next
end foreach

if (|possibleStartNodes| != 1) fail

let currentNode = the one node in possibleStartNodes
let ordering = new list
ordering.push(currentNode)

while (nexts contains value for currentNode) 
  ordering.push(next)
  currentNode = next
end while

return ordering

$O(n)$ 对我来说看起来很合理。有什么方法可以改进吗？

编辑： 对于我正在使用的概念的正确技术术语的任何提示，我将不胜感激

Answer 2

这是一个非常非最佳的算法，可以帮助您入门。

遍历所有边缘 $(a,b)$. 。对于每条边，再次检查所有边，并检查次数 $a$ 出现。一旦发现就停止 $a$ 只出现一次（如果这种情况从未发生，则拒绝）。我们将采取 $n_1 = a$.

再次遍历所有边缘，寻找独特的边缘 $(n_1,b)$ 其中 $n_1$ 出现。拿 $n_2 = b$.

再次遍历所有边缘，寻找边缘 $(n_2,c)$ 其中 $n_2$ 出现在左侧（如果没有这样的边缘，则拒绝）。拿 $n_3 = c$.

如此继续下去，发现 $n_4,\l点,n_n$.

该算法运行于 $O(n^2)$. 。使用哈希，您应该能够将其改进为 $O(n)$.