すべての最小スパニング ツリーを見つけたいわけではありませんが、それらがいくつあるかを知りたいのですが、これが私が検討した方法です。
- プリムまたはクラスカルのアルゴリズムを使用して 1 つの最小スパニング ツリーを見つけてから、すべてのスパニング ツリーの重みを見つけ、最小スパニング ツリーの重みと等しい場合にランニング カウンターをインクリメントします。
すべてのスパニング ツリーの重みを見つける方法が見つかりませんでした。また、スパニング ツリーの数が非常に多い可能性があるため、この方法は問題に適していない可能性があります。最小スパニング ツリーの数は指数関数的であるため、数え上げるのは得策ではありません。
- すべての重みは正になります。
- また、グラフに 3 回以上表示される重みはないと仮定することもできます。
- 頂点の数は 40,000 以下になります。
- エッジの数は 100,000 以下になります。
頂点の重みが異なるグラフ内の最小全域木は 1 つだけです。最小全域木の数を求める最良の方法は、この性質を利用したものに違いないと思います。
編集：
この問題の解決策を見つけましたが、なぜ機能するのかわかりません。誰か説明してくれませんか。
解決策: 最小スパニング ツリーの長さを求める問題は、かなりよく知られています。最小スパニング ツリーを見つけるための 2 つの最も単純なアルゴリズムは、Prim のアルゴリズムと Kruskal のアルゴリズムです。これら 2 つのうち、Kruskal のアルゴリズムは重みの昇順でエッジを処理します。ただし、Kruskal のアルゴリズムには考慮すべき重要なポイントがあります。重みで並べ替えられたエッジのリストを検討する場合、エッジを貪欲にスパニング ツリーに追加できます (ただし、何らかの方法で既に接続されている 2 つの頂点を接続しない限り)。 ）。
ここで、クルスカルのアルゴリズムを使用して部分的に形成されたスパニング ツリーを考えます。長さが N 未満のいくつかのエッジを挿入したので、長さが N のエッジをいくつか選択する必要があります。アルゴリズムは、可能であれば、長さが N を超えるエッジの前にこれらのエッジを挿入する必要があると述べています。これらのエッジを任意の順序で挿入します。また、挿入するエッジに関係なく、グラフの接続性はまったく変更されないことに注意してください。(頂点 A から頂点 B へのエッジがあるグラフとないグラフの 2 つの可能なグラフを考えてみましょう。2 番目のグラフは、同じ接続コンポーネントの一部として A と B を持っている必要があります。そうでない場合、A から B へのエッジはワンポイント。）
これら 2 つの事実は一緒に、Kruskal のアルゴリズムを使用して長さ K のエッジを挿入する方法の数の積になることを意味します (K の可能な値ごとに)。任意の長さのエッジが最大で 3 つあるため、さまざまなケースが力ずくで実行される可能性があり、接続されたコンポーネントは通常どおり各ステップの後に決定できます。