問題タブ [minimum-spanning-tree]

トーナメント グラフの支配的なセットを見つけるアルゴリズムを作成しています。有向グラフの最小全域木は、グラフの支配集合と同等ですか? 言い換えれば、トーナメント グラフの最小の MST を (すべての頂点を反復することによって) 見つけた場合、これはグラフの支配的なセットと同等であると言えますか?

私の問題は、グラフ内の最小スパニング ツリーを見つけることです。しかし、各頂点の合計次数が一定の係数を超えてはならないというもう 1 つの制約が必要です。問題をモデル化するにはどうすればよいですか? MST は間違ったパスですか? 私に役立つアルゴリズムを知っていますか？

もう 1 つの問題: グラフのエッジの重みが重複しているため、一意の MST の数をカウントする方法はありますか? これを行うアルゴリズムはありますか?

ありがとうございました。

編集：度とは、頂点を接続するエッジの総数を意味します。重複するエッジの重みとは、2 つのエッジの重みが同じであることを意味します。

Prim のアルゴリズムをいつ使用し、 Kruskal の最小スパニング ツリーをいつ見つけるべきなのか疑問に思っていました。どちらも簡単なロジックで、最悪のケースも同じです。唯一の違いは、データ構造が少し異なる可能性がある実装です。では、決め手は何ですか？

Prim のアルゴリズムを C (www.bubblellicious.es/prim.tar.gz) で実装しましたが、これをKruskal のアルゴリズムに変換する方法を考えていました。

それらは非常に似ているようですが、古いコードを新しいコードに変更する方法が想像できません。アドバイスなど頂ければ有難いです。それが簡単なのはわかっていますが、私はまだ C プログラミングの初心者です ...

私は2セットのAnimalオブジェクトを持っています。動物間の距離は、その特性を調べる特定のアルゴリズムを使用して定義されます。距離を最小化する 2 つのセット (それぞれから 1 つ) からペアを見つける方法を設計しようとしています。

私が持っていたアイデアの 1 つは、パラメーター化Tupleされたクラスを作成してペアを組むことAnimalsです。2 つのメンバー間の距離に従ってPriorityQueue並べ替えるには、コンパレータを使用して を作成します。Tuple<Animal>次に、 から最初のペアを選択しPriorityQueueます。

これは良いデザインですか、それとも無駄ですか？m と n が各コレクションのサイズである場合、O(m+n) 時間で実行されると思います。

パラメータ化されたクラスの場合Tuple、でのみ機能する Comparator を使用するとどのように機能しAnimalますか?

findMinimalPairこの方法を使用して、オブジェクトのグラフの距離を最小化するスパニング ツリーを作成したいと考えていAnimalます。からペアを継続的にポップしPriorityQueue、各ペアに各コレクションのメンバーが 1 つずつ含まれていることを確認して、これを行ったらどうなるでしょうか。

これが基本的な例です。距離は次のとおりです。

コレクションが次のとおりであると仮定します。

A0

A1、A2、A3

タプルを距離順にソートすると、次のようになります。

したがって、A3 が最も近いことがわかります。次に、A3 が最初のコレクションに移動されます。

A0、A3

A1、A2

繰り返しますが、最小ペアを確認します。

今A2が取られています。それがどのように機能するか見てください。

これが私がやったことです。コメント?

プリム法を使用してMSTを解決するコードを作成しました。この種の実装（優先キューを使用）はO（E + VlogV）= O（VlogV）である必要があることを読みました。ここで、Eはエッジの数、Vはエッジの数ですが、コードを見ると単純に見えません。誰かが私のためにこれを片付けることができれば私はそれをいただければ幸いです。

私には、実行時間はこれであるように思われます：

whileループにはO（E）回かかります（すべてのエッジを通過するまで）そのループ内で、O（logE）時間かかるQから要素を抽出します。そして、2番目の内側のループにはO（V）時間がかかります（すべての頂点を追加する必要があるため、このループがV回実行されることは明らかですが、毎回このループを実行するわけではありません）

私の結論は、実行時間は次のとおりです。O（E（logE + V））= O（E * V）。

これは私のコードです：

基本的にグラフとして表示できる問題があります。私は自分自身をロールバックする代わりに、JGraphT を使用して実装することを検討しています。JGraphT を使用してグラフから最小スパニング ツリーを取得する最良の方法は何でしょうか?

JGraphTには素晴らしいフィボナッチヒープクラスがあります。これを使用して、プリムの最小スパニングツリーアルゴリズムを実装するにはどうすればよいですか？

JGraphT で Prim の最小スパニング ツリー アルゴリズムを実装しようとしています。それはどのように見えますか？

私が遭遇した 1 つの問題は、JGraphT が指示どおりにすべてを処理することでした。そのため、リバースするためにいくつかのぎこちない呼び出しを行う必要がg.getEdgeSource(e)ありg.getEdgeTarget(e)、それらがたまたま正しくなかった場合があります。

JGraphT の Fibonacci Heap を使ってこれを最初に実装しようとしましたが、難しすぎたので、通常の PQ を行いました。

存在しないエッジの重みを無限に設定する代わりに、それをキューに追加しませんでした。

アドバイス？スタイルの問題？明らかな非効率性？独自のコードをロールバックする代わりに使用する必要があるコードはありますか?

プリムのアルゴリズムを使用してグラフの最小スパニングツリーを見つける場合、どのルートノードを選択するかは問題ではなく、結果のMSTの重みは同じになると直感的に感じます。これは正しいです？