遍历给定大小的所有树

问题描述：

我经常面临通过强力检查给定大小树的某些属性（图形）的问题。你有这样做的好手段吗？理想情况下，我想只检查一次同构类（但毕竟，速度是重要的）。遍历给定大小的所有树

位操作技巧是最欢迎的，因为n通常小于32 :)

我通过所有（N-1）〜边缘亚群和检查要求稍微更精细的算法比“循环喜欢如果它们在n个节点上形成树“。

什么样的树？你目前使用什么算法来“穿越”树？你在谈论什么同构论？这个问题非常含糊 – 2011-02-13 18:32:01

一般树，即连接n个节点和n-1个边的图。同构我的意思是en.wikipedia.org/wiki/graph_isomorphism。我没有穿过特定的树 - 我想生成所有树的列表。 – Erik 2011-02-13 18:52:38

答

这是Knuth的计算机编程艺术卷组合算法。如果我没有记错，那是一个练习。既然他有这样的解决方案，我指你在那里。

答

一些谷歌搜索引起了下面的算法描述：http://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf。他们修改了一个枚举根树的算法来枚举无根树。

显然其他人证明，这种只需要每棵树分期常量时间，PDF显示了一些性能测试证明这一点。