問題タブ [kruskals-algorithm]

私が受講したプログラミングの授業では、Bellman-Ford SSSP と Djikstra の SSSP を学び、Bellman-Ford は Kruskal の最小スパニング ツリー アルゴリズムに基づいており、Djikstra のアルゴリズムは Prim の最小スパニング ツリー アルゴリズムに基づいていることを学びました。

すでに選択されているエッジとノードに基づいて比較を行うため、Djikstra と Prim は両方ともローカル レベルで動作することを覚えておくように言われましたが、これは理にかなっています。また、Bellman-Ford と Kruskal は、以前に選択したノードに関係なく最小のエッジ ウェイトを選択するため、グローバル レベルで動作したことを覚えておくように言われました。

Kruskal のアルゴリズムの場合、これがグローバルであると見なされる理由は理解できます。文字通り、最も軽いまたは最小のエッジの重みを選択するだけだからです。しかし、Bellman-Ford のアルゴリズムについては、以前に選択したノードとエッジについて心配する必要があるため、グローバルであると見なされる方法がわかりません。Bellman-Ford は、いったいどのように Kruskal のアルゴリズムに基づいているのでしょうか。

ビデオに基づいて、クラスカルのアルゴリズムを書きました。しかし、私には「小さな」問題があります-最低の重みを見つける代わりに、最高の重みを見つけます。おかしく聞こえるかもしれませんが、どこを間違えたのかわかりません。

そしてメインアルゴリズム。重みは、「weightmat」と呼ばれる 2 次元マトリックスに保持されます。Vertex は頂点の量、Edges は変数 v1、v2、weight を持つ構造体です。この構造体を使用して、エッジの配列を作成します。:

次のコードは、隣接行列から最小スパニング ツリーを見つけることになっています。

6 つの頂点と次の行列で機能します。

ただし、13 個の頂点と次の行列の場合:

このエラーが発生します：

エラーは 17 行目で発生します。while (parent[i])

VSオート:

選択したエッジがサイクルを形成せず、選択したすべてのエッジの重みの積が最大になるようにグラフからエッジを選択することを目的とする codechef の質問を見ました。社説では、プリムとクルスカルのアルゴリズムが機能することが示されています。 here.実際、エッジの対称単調関数を最大化するために機能することが与えられています。では、対称単調関数とは正確には何であり、このアルゴリズムを他にどこで使用できるのでしょうか。

基本的に、頂点 u と v が同じコンポーネントにないかどうかを確認する以外に、もう 1 つの条件を追加して、クラスカルのアルゴリズムを変更しようとしています。ユニオン検索データ構造がどのように機能するかを漠然と理解しているので、実際に正しい考えを持っているかどうかを確認したかった.

無向グラフ G = (V, E) と、V のいくつかの頂点 (頂点 A ⊂ V のサブセット) を含む集合 A があるとすると、V の頂点 u ごとに (ループ) 、u もこのセット A に含まれています。

設定されたパラメーターが異なる (つまりラベルが異なる) ため、これは機能しませんか? 確認したかっただけなのに…

明確にするために、エッジ (u, v) にセット A の頂点の 1 つが含まれているかどうかを知る必要があります。そして、これを達成するために Union-Find を使用しようとしていました (find() には O(1) 時間がかかるため)。セット A をトラバースして各要素を比較する代わりに...これが可能かどうか誰か教えてもらえますか? それとも、配列トラバーサル メソッドを使用する必要がありますか?

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

クラスカルのアルゴリズムを Java で実装する必要があります。

エッジを重み順に並べる部分があるのですが、各木の集合を保存する構造を考えないといけないので少し迷います。

各セットがツリーを表すセットのベクトルを持つことを考えました。しかし、2 つのツリーを結合する必要がある場合、どうすればよいかわかりません。ベクターから両方の要素を削除し、結合された新しい要素を追加しますか?

それを簡単にする構造はありますか？

私が必要とするのは：

• 主要なセットからすべてのセットを反復する
• セットの 1 つに要素を追加するか、または
• 新しいセットを作成してメジャー セットに追加する
• それらのセットの 2 つを結合します (もちろん、それらの特異なバージョンを削除します)