遍历给定大小的所有树
我经常面临通过强力检查给定大小的树（图形树）的某些属性的问题。你有什么好的技巧吗？理想情况下，我只想检查每个同构类一次（但毕竟，速度才是最重要的）。
位旋转技巧是最受欢迎的，因为 n 通常小于 32 :)
我要求比“循环遍历所有 (n-1) 边子集并检查它们是否形成树”之类的树稍微更精细的算法在 n 个节点上。
I am often faced with the problem of checking some property of trees (the graph ones) of a given size by brute force. Do you have any nice tricks for doing this? Ideally, I'd like to examine each isomorphism class only once (but after all, speed is all that matters).
Bit twiddling tricks are most welcome since n is usually less than 32 :)
I'm asking for slightly more refined algorithms than the likes of "loop through all (n-1)-edge subsets and check if they form a tree" for trees on n nodes.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是高德纳 (Knuth) 的《计算机编程艺术》一书中有关组合算法的内容。如果我没记错的话，那是一个练习。既然他有解决方案，我就向你指出。
This is in Knuth's The Art of Computer Programming volume on Combinatorial Algorithms. If I remember correctly, it's an exercise there. Since he has the solutions for such, I point you there.
一些谷歌搜索出现了以下算法描述：http://www. cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf。他们采用了枚举有根树的算法来枚举无根树。
显然其他人已经证明这只需要每棵树摊销恒定时间，并且 PDF 显示了一些性能测量来证明这一点。
Some googling turned up the following algorithm description: http://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf. They adapt an algorithm for enumerating rooted trees to enumerating unrooted trees.
Apparently others have proved that this requires only amortised constant time per tree, and the PDF shows some performance measurements demonstrating this.