我经常面临通过蛮力检查给定大小的树（图形）的某些属性的问题。你有什么好的技巧吗？理想情况下，我只想检查每个同构类一次（但毕竟，速度才是最重要的）。
最受欢迎的小技巧是因为 n 通常小于 32 :)
对于 n 个节点上的树，我要求比“遍历所有 (n-1) 边子集并检查它们是否形成树”之类的算法稍微更精细一些。
问问题
279 次
2 回答
3
这是 Knuth 关于组合算法的计算机编程艺术卷。如果我没记错的话，那是一个练习。既然他有这样的解决方案，我指出你那里。
于 2011-02-13T18:41:51.923 回答
0
一些谷歌搜索出现了以下算法描述：http ://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf 。他们采用了一种用于枚举有根树的算法来枚举无根树。
显然，其他人已经证明这仅需要每棵树的摊销常数时间，并且 PDF 显示了一些性能测量来证明这一点。
于 2011-02-13T22:47:50.227 回答