問題タブ [kruskals-algorithm]

Kruskal のアルゴリズムを使用して最小全域木を生成しましたが、パスを格納する方法を知りたいと思っていました。

これは私の最小スパニングツリーです

Kruskal アルゴリズムを使用してこの最小スパニング ツリーを生成しましたが、2 つのノード間のパスを生成するのに苦労しました。誰かが擬似コードで私を助けることができますか? Adjacency List と Adjacency Matrix を使ってみた

クラスカルのアルゴリズムをテストするために、単純な無向グラフを生成する必要があります。次のように作成された、すべての接続の構造があります。

ここで、Kruskal をテストするために、これらの接続を適切な量生成する必要があります。Kruskal のアルゴリズムは、この世代ほど難しくはありませんでした。グラフに直面するのはこれが初めてだったからかもしれません。

JAVA の MST アルゴリズムに問題がありますか?

JavaでMSTのコードを書こうとしています

ここで、グラフは既に与えられており、ノード (パス上ではない) を追加する addCheapest メソッドを記述しようとしています。これは、パスに追加されると、ある位置で、グラフ内のすべてのノードとすべての位置のパスの結果のコストを最小化します。それらは追加できます。その位置に追加します。

}*

特定のエッジ (u,v) を含める必要があるように、最小スパニング ツリーのクラスカルのアルゴリズムを変更する方法を考えられる人はいますか?

だから私は割り当てがあり、コードを書くことができましたが、それは機能しますが、大きな数字では遅すぎて、改善を手伝ってくれるかもしれません.制限時間は3秒です. いくつかのアイデアを聞きたいです。この割り当てでは、最小スパニング ツリーを見つける必要があります。

入力は次のようになります。

出力は最小値になります。MST の距離。MST がない場合、出力は -1 になります。

例を次に示します。

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

Kriskal のアルゴリズムを C++ で実装しようとしていますが...

DAA.exe の 0x0127160d で未処理の例外: 0xC0000005: アクセス違反の読み取り場所 0xdd2021d4。

getRoot 関数の次の行で停止します。

while(都市[ルート].prev != NO_PARENT)

問題は都市配列のデータにあると思います。配列内のすべてのデータを印刷すると、それは私が望むものではありません。都市の名前は、「════════════════¤¤¤¤ллллллллю■ю■」と数字 (int) - (-842150451) のようになります。以下は完全なコードです。

以下は、CSアルゴリズムの講師によるクラスカルの最小スパニングツリーアルゴリズムの擬似コードです。MSTアルゴリズムが非決定論的であるかどうかを知りたいと思いました。同じ重みを持つ2つのエッジが与えられた場合、Tに追加するときにどちらのエッジもサイクルを形成しなかった場合、アルゴリズムはどのようにそれらを決定しますか。確かにランダムである場合、Tに追加された正確なエッジの結果を判断できません。

ありがとう！

重みのある無向連結グラフが与えられます。w:E->{1,2,3,4,5,6,7} - 可能な重みは 7 つしかないことを意味します。O(n+m) の Prim のアルゴリズムと O( m*a(m,n)) の Kruskal のアルゴリズムを使用してスパニング ツリーを見つける必要があります。

これを行う方法がわかりません。ここでウェイトがどのように役立つかについてのガイダンスが本当に必要です.

G = (V,E) を無向グラフとします。エッジのセット F ⊆ E は 、G のすべてのサイクルが F に少なくとも 1 つのエッジを持つ場合、フィードバック エッジ セットと呼ばれます。

(a) G が重み付けされていないと仮定します。最小サイズのフィードバック エッジ セットを見つける効率的なアルゴリズムを設計します。

(b) G が正の辺の重みを持つ重み付き無向グラフであるとします。最小重みフィードバック エッジ セットを見つけるための効率的なアルゴリズムを設計します。

私の解決策（提案が必要）：

a)最小サイズのフィードバック エッジ セット:グラフは重み付けされていないため、DFS を使用できます。通常どおり、任意の頂点から DFS を開始します。バック エッジに遭遇すると、それをフィードバック エッジのセットに挿入します。DFSが完了すると、セットが答えになります。

b)最小重みフィードバック エッジ セット:グラフが重み付けされているため、Kruskal を使用できます。しかし、クラスカルは通常、ウェイトが最も小さいエッジから始めます。すべての辺の重みを無効にしてから Kruskal を実行できれば、同じコンポーネントの頂点間の辺を取得するたびに、それをフィードバック エッジ セットに保存できます。最後に、エッジの重みを無効にします。エッジの重みを無効にすることを提案する理由は、最小の重みフィードバック セットが必要だからです。負の重みを使用すると、Kruskal は重みが最小 (実際には最大) のエッジから開始し、重みが小さい同じコンポーネントのエッジを見つけます。

この解決策が正しいかどうかを誰かが知ることができますか?