問題タブ [kruskals-algorithm]

Kruskal のアルゴリズムを実装しますが、ウェイトを使用して形状を描画する方法はありますか? 残りの作業を行うことができるように、ユーザーが数字で下の形状を何らかの方法で描画することを望みます。

それは可能ですか？はいの場合、どのように？アイデアが必要です。

UVA OnlineJudge の問題 #10034 の解決策として、次のコードを書きました。

問題で提供されたテストケースと、ここで見つけたより大きなテストケースの両方で機能します: http://online-judge.uva.es/board/viewtopic.php?p=21939#p21939

しかし、UVA に送信すると、間違った回答メッセージが表示されます。Krukal のアルゴリズムの実装は正しいですか? 私は何を間違っていますか？

グリッドは、次の 2 つの配列に格納されたエッジを使用してイメージを定義します。

• h[x][y]x,yからまでの辺の重みを与えるx+1,y
• v[x][y]x,yからまでの辺の重みを与えるx,y+1

クラスカルのアルゴリズムを実装しようとしています。これはかなり簡単です。オンラインで実装を見つけてコピーできます。問題はエッジの処理です。具体的には; それらを並べ替えると混乱します。

このテイクのエッジを具体的に保存するより良い方法はありますか? 私はそれらがすべてのピクセルから隣接するピクセルまでであることを望みます。画像を i[x][y] として保存しています。エッジの重みは画像値の差です。

入力に対してこのコードを実行できます。しかし、場合によっては、間違ったスパニング ツリーを取得します。例：プログラムの実行中に次のように入力した場合：

頂点の数を入力してください: 5 エッジの数を入力してください: 8

私の間違いを正すために親切に助けてください... plsは、私がコードで行った変更を教えてください.. plssss

コードは次のとおりです。

Disjoint set Data Structures と Kruskal のアルゴリズムを OpenCL で実装したいと考えています。OpenCL でいくつかのコードを実装しましたが、OpenCL でデータ構造を開始する方法がわかりません。Aftab Munshi の本に記載されている Djkstra のアルゴリズムは理解しにくいものです。誰かが別の情報源を提案できますか...?

素集合を使用してクラスカルのアルゴリズムの実装を作成しようとしています。ほぼ機能していると思いますが、コードの一部を正しく機能させることができないようです。コードは、グラフ上のノードが、追加しようとしているセットに既に含まれているかどうかを確認する必要があります。それ以外の場合は、追加したくありません。私が使用しているコードは次のとおりです。

ちょっとした情報: このメソッドは、2 つのノードが既に同じセットにあるかどうかを判断しています。ノード配列には、グラフ上のすべてのポイントが含まれます (ノードは、x 値と y 値を格納するだけのクラスであり、それらを取得できます。セットは、ノードの ArrayLists の配列です。問題の開始時に、すべてのノードはArrayList 自体; 最終的に、それらはすべて同じ ArrayList にある必要があります. インデックス 1 と 2 は Nodes 配列のノードに対応します.

残念ながら、このコードでは正しい出力が得られないようです。私はそれを1時間以上見つめていましたが、何が問題なのか理解できませんでした.

前もって感謝します。

G = (V, E) を重み付き連結無向グラフとします。Kruskal のアルゴリズムで成長し、k 回の反復後に停止するエッジ セットを T とします (したがって、T には |E|-1 未満のエッジが含まれる可能性があります)。W(T) をこのセットの加重和とします。T' を |T| となるアシル エッジ セットとする。= |T'|。W(T) <= W(T') であることを証明する

私はアルゴリズムの元の証明を理解しており、これに取り組むためにいくつかのアプローチを試みましたが、どちらもうまくいきませんでした。

例: |T| に関する帰納法を考えました。動作する可能性があります。|T| の場合 = 1 明らかです。

|T|=k の正しさを仮定し、k+1 の正しさを証明します (または…)。矛盾により、|T'|=k+1 かつ W(T') < W(T) となる辺集合 T' が存在するとします。

Kruskal アルゴリズムによって追加された最後のエッジを e とします。したがって、T' の任意のエッジ f について、W(f) < W(e) (そ​​うでない場合、2 つのセットからエッジを削除し、矛盾が発生します)。

これは、T' のすべてのエッジが既に T にあるか、T – {e} でサイクルを形成している場合にのみ発生します。

…</p>

注: クラスカルのアルゴリズムと同じ証明ではありません。T' が接続されているかどうかさえわかりません。

次に何をすべきかわかりません。助けていただければ幸いです、事前に感謝します

G =（V、E）を重み付きの接続された無向グラフとし、Tを最小全域木とします。eをEにない（そして重みW（e）を持つ）任意のエッジとします。証明または反証：TU {e}は、G'=（V、EU {e}）の最小全域木を含むエッジセットです。

まあ、それは私には真実に聞こえるので、私はそれを証明することに決めましたが、私は毎回立ち往生しています...

たとえば、eが最小の重みを持つ新しいエッジである場合、Tのエッジが、Eの他のエッジの「ヘルプ」なしで新しい最小の重みを取得するのを妨げるような悪い方法で選択されていないことを約束できます。 -T？

助けていただければ幸いです。よろしくお願いします。

G =（V、E）を重み付きの接続された無向グラフとし、eをEの任意のエッジとします。エッジeを含む最小全域木が存在するかどうかを決定する線形時間アルゴリズムを示します。

私は質問1の奇妙な「解決策」を見つけることができました。それはうまくいくようですが、線形ではないと思います。

彼らは、W（u、v）<W（e）となるように、各エッジ（u、v）に対してunion find and do Union（u、v）を使用することを提案しました。ここで、e =（x、y）と仮定します。ここで、find（x）！= find（y）の場合、xとyは接続されておらず、W（e）はクラスカルのアルゴリズムによって調べられる次の重みになるため、エッジを含むMSTが確実に存在します。 e。

一方、find（x）= find（y）の場合、この時点までクラスカルアルゴリズムを実行すると、xとyが確実に接続されるため、エッジeをMSTに追加することはできません（重みが等しいエッジの並べ替え順序-クラスカルのアルゴリズムを使用して、任意のMSTを作成できます）。

なぜこれが線形なのかわかりませんか？組合のせいでO（| E | alpha（| V |））の費用がかかるのではないですか？

おそらく、線形時間でこれを行う別の方法がありますか？

前もって感謝します

G = (V, E) を重み付き連結無向グラフとします。G に 2 つの異なる MST があるかどうかを判定する効率の良いアルゴリズムを説明してください。

私がすでに解決した前の問題は、はるかに簡単でした: G に MST が 1 つだけ存在するかどうかを決定する効率的なアルゴリズムを説明してください。

これが私が後者の質問を解決した方法です：

Kruskal アルゴリズムを実行し、新しい MST のエッジを青で、残りのエッジを赤で色付けします。

次に、これまでに見た (Kruskal を使用する) 別の単純なアルゴリズムを使用しました。このアルゴリズムは、最大数の赤いエッジを含むグラフ内の MST を見つけます。つまり、エッジの色に関係なく、グラフ G 内の MST であり、他のすべての MST には、アルゴリズムが検出した MST よりも多くの赤いエッジを含めることはできません。

これで、アルゴリズムが同じ MST (すべての青いエッジを含む) を見つけた場合、MST は 1 つだけになります。

ここでのもう 1 つの質問は、もっと複雑に思えます。上記のアルゴリズムを使用してみましたが、他のさまざまなトリックも使用しようとしましたが、どちらも機能しませんでした。

ところで、グラフ内の異なる MST の数をカウントするアルゴリズムがあると聞いたことがありますが、それは実際にはやり過ぎであり、単純なアルゴリズムを提供するよう求められました。

助けていただければ幸いです、ありがとう