問題タブ [kruskals-algorithm]

特定のグラフから最小スパニング ツリー (MST) を取得しました。任意の 2 つの頂点の一意のサブパス (グラフではなく、MST の一部である必要があります) を計算しようとしていますが、効率的な方法を見つけるのに苦労しています。

これまでのところ、クラスカルのアルゴリズム (Disjoint Data 構造を使用) を使用して MST を計算しました (例: A から J までの 10 個の頂点)。 (グラフが無向であると仮定します)。

任意の提案をいただければ幸いです。

あるサイトを見ていたらこんな写真が目に留まりました。

私の意見では、それは間違っています、

ご覧のとおり、ES、GI、DF、EF は、この図の最初の 4 つとして示されています。

ES、GI、DF、DSじゃないの？

字句順になっているはずだったのに、なぜ正解としてマークされているのですか? 私は何が欠けていますか？

PS、これは私の大学の試験問題の 1 つでした。

最小スパニング ツリーの重みを見つけるには、boost ライブラリの kruskals アルゴリズムを使用する必要があります。私はそれを管理したと思います

ここで、頂点 0 とそこから最も遠い頂点の間の距離 (重みの合計) を見つける必要がありますか? どうすればそれができるかについてのヒントはありますか？

頂点イテレータを使用することを考えていましたが、重みを weightMap に格納するので、グラフの頂点を反復処理する場合、どのようにアクセスすればよいでしょうか?

編集: プログラムを修正し、kruskal と prim を使用することにしました

1. スパニング ツリーの重みの kruskal 2. 頂点 0 からの各頂点の距離の prim アルゴリズム (マップの距離に格納されているスパニング ツリー内)

残念ながら、何かがうまくいかず、3 番目の頂点である距離 [*頂点] は答え 2 を与えませんが、1 を与えます

また、スパニング ツリーの重みは 7 ではなく 14 です。

私のダミー入力は次のとおりです。

ここに私のプログラム：

ありがとうございました ：）

クラスカルのユニオン検索アルゴリズムを実装しようとしています。私はこの疑似コードを使用していますが、以下のユニオン部分のステップ 2 (再帰呼び出しではない) を理解していないか、私が近いかどうかさえわかりません。この方法がうまくいかない場合は、理解できる限り、どの実装でも使用できます。事前に感謝します。U と V は私のエッジ ノードで、今のところ int です。

ステップ2がわかりません。これまでのコードは次のとおりです。

私は最小スパニング ツリーの分析を行っていましたが、ソート時間がクラスカルのアルゴリズムの全体的な時間の複雑さにどのように影響するのか疑問に思っていました。

例：

1. 並べ替えができる場合O(n log log n)
2. 並べ替えができる場合O(n)

答えは両方の場合にまだ残っO(e log n)ていますか、それとも変わりますか?