python - すべての最小スパニングツリーの実装

Question

無向加重グラフのすべての最小スパニングツリー（MST）を見つける実装（networkxライブラリを使用しています）を探していました。

クラスカルのアルゴリズムとプリムのアルゴリズムの実装しか見つかりません。どちらも単一のMSTしか返しません。

この問題に対処する論文（カウントと生成へのアプリケーションですべての最小スパニングツリーを表すなど）を見たことがありますが、コードに変換する方法を考えようとすると、頭が爆発する傾向があります。

実際、私はどの言語の実装も見つけることができませんでした！

Answer 1

これが解決策かどうかはわかりませんが、解決策です（ブルートフォースのグラフバージョンだと思います）：

1. クラスカルまたはプリムのアルゴリズムを使用して、グラフの MST を見つけます。これは O(E log V) である必要があります。
2. すべてのスパニング ツリーを生成します。これは で実行できますO(Elog(V) + V + n) for n = number of spanning trees。2 分間の Google で理解しているように、おそらく改善される可能性があります。
3. ステップ 2 で生成されたリストを、ツリーの重みが MST の重みと等しくなるようにフィルタリングします。これは、ステップ 2 で生成されたツリーの数として、n に対して O(n) である必要があります。

注: これは怠惰に行ってください。可能なすべてのツリーを生成してから結果をフィルタリングすると、O(V^2) メモリが必要になり、多項式スペースの要件は悪です-ツリーを生成し、その重みを調べます。MST の場合は結果リストに追加し、そうでない場合は破棄します-破棄します.
全体的な時間の複雑さ:O(Elog(V) + V + n) for G(V,E) with n spanning trees

Answer 2

Ronald Rivestには、Python、mst.pyでの優れた実装があります。

Answer 3

Sorensen と Janssens (2005)の研究でアイデアを見つけることができます。

アイデアは、増加する順序で ST を生成し、ST の値が大きくなるとすぐに列挙を停止することです。