与えられたサイズのツリー (グラフのもの) のいくつかのプロパティを強引にチェックするという問題に直面することがよくあります。これを行うための良いトリックはありますか？理想的には、各同型クラスを 1 回だけ調べたいと思います (ただし、重要なのは速度だけです)。
n は通常 32 未満であるため、ビットをいじるトリックは大歓迎です :)
n ノード上のツリーに対して、「すべての (n-1) エッジ サブセットをループし、それらがツリーを形成するかどうかを確認する」ようなものよりも、少し洗練されたアルゴリズムを求めています。
これは、コンビナトリアル アルゴリズムに関する Knuth の The Art of Computer Programming ボリュームにあります。私の記憶が正しければ、そこは演習です。彼はそのような解決策を持っているので、そこを指摘します。
いくつかのグーグルは、次のアルゴリズムの説明を見つけました: http://www.cs.auckland.ac.nz/compsci720s1c/lectures/mjd/treenotes.pdf。それらは、ルートのあるツリーを列挙するアルゴリズムを、ルートのないツリーを列挙するアルゴリズムに適合させます。
どうやら他の人は、これがツリーごとに償却された定数時間だけを必要とすることを証明しており、PDF はこれを実証するいくつかのパフォーマンス測定値を示しています。