0

我需要一种算法来计算给定树结构的所有可能排列，例如： 

4      3  
 \     |  
  \    2
   \  /  
    1

这意味着，(4) 需要在 (1) 之前排序，(3) 在 (2) 之前和 (2) 在 (1) 之前排序。因此输出应该包含所有且不超过以下内容：

[4,3,2,1]  
[3,4,2,1]  
[3,2,4,1]

例如，无效的订单是

[4,2,3,1]

因为 (2) 在 (3) 之前，但 (2) 在图中是 (3) 的后继。出于效率的原因，简单地计算所有排列和过滤无效排序是行不通的。

我不需要确切的代码，了解通常如何做到这一点已经非常有帮助。

4

2 回答 2

1

这个问题是对有向图进行拓扑排序。
它可以通过时间复杂度 O(E+V) 的 DFS 来解决。
http://en.wikipedia.org/wiki/Topological_sorting

于 2013-10-07T19:18:48.007 回答
0

如果有人仍然对此感兴趣，我的问题的算法已经在 70 年代由 Varol 和 Rotem 在他们的论文“生成所有拓扑排序安排的算法”中提出。
实际上搜索拓扑排序会帮助我更早地找到解决方案，但是，可以在这里找到这篇文章：http: //comjnl.oxfordjournals.org/content/24/1/83.abstract

于 2013-10-15T09:29:44.057 回答