遍歷給定大小的所有樹

Question

我經常面臨通過強力檢查給定大小樹的某些屬性（圖形）的問題。你有這樣做的好手段嗎？理想情況下，我想只檢查一次同構類（但畢竟，速度是重要的）。

位操作技巧是最歡迎的，因爲n通常小於32 :)

我通過所有（N-1）〜邊緣亞羣和檢查要求稍微更精細的算法比「循環喜歡如果它們在n個節點上形成樹「。

Answer 1

這是Knuth的計算機編程藝術卷組合算法。如果我沒有記錯，那是一個練習。既然他有這樣的解決方案，我指你在那裏。

Answer 2

一些谷歌搜索引起了下面的算法描述：http://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf。他們修改了一個枚舉根樹的算法來枚舉無根樹。

顯然其他人證明，這種只需要每棵樹分期常量時間，PDF顯示了一些性能測試證明這一點。