問題タブ [prims-algorithm]

最小スパニング ツリーを導出するための Prim のアルゴリズムの実装をコーディングしています。My Graph は、Map<String, ArrayList>キーが州名に対応し、値が両方のリンクへのポインターを保持するエッジです。

プリムのアルゴリズムでは、開始ノードのみを含むツリーから開始し、ツリーがグラフと同等になるまでループする必要があります。TreeMap<String, ArrayList>aとの同等性を判断するにはどうすればよいMap<String, ArrayList>ですか?

プリムのアルゴリズムとダイクストラのアルゴリズムの違いを知っています。前者は MST を生成し、後者はソースからすべてのノードへの最短パスを提供します。数学的には、これらは同じではないため、2 つのアルゴリズムが常に同じ結果を生成するとは限りません。

ただし、さまざまな例を試してみると、同じ結果が得られます。Prim のアルゴリズムと Dijkstra のアルゴリズムの疑似コードも非常によく似ています。Prim が生成する MST が、Dijkstra で解決しているときに得られない、またはその逆の例を教えてください。

また、私の知識によると。これらのアルゴリズムは両方とも、次のアプローチを使用します。私が間違っている場合は修正してください：

すでに含まれているセットの i とまだ含まれていないセットの j で最短の ij を見つけ、j をセットに追加します。

フィボナッチ ヒープのキーの減少操作で O(1) の償却複雑さを取得するにはどうすればよいですか? 要素を含むフィボナッチ ヒープ内のノードを見つけるだけでも、BFS を使用して O(n) 時間かかるため、O(1) 償却時間を取得することはできません。

参考までに、問題のノードを検索するための BFS の実装を次に示します。

そして、ここに私の減少キーのコードがあります:

プリムのアルゴリズムを実装するプログラムを作成しましたが、正常に動作しません。頂点はプライオリティ キューで変更されています。1 つの頂点は重みと親を変更しません。

コードは

出力は次のとおりです。

私の正しい MST Kruskal Algorithm からの出力は

コードを評価しているときに、ヒープが正常に機能していないことがわかりました。頂点 5 が抽出されると、その重みは 4 で、親は -10 になります。これは、重みが減少したかのように発生するべきではなく、親が存在する必要があります。そしてその時点で、他の頂点は対応する親に対して間違った重みを持っています。

編集: 問題は heapdecrease 関数にあるようです。隣接リストをトラバースした後に buildminheap を呼び出す場合。その後、正しい結果が得られます。heapdecrease 関数は私の知る限り正しいですが、間違っています。

これは過去の試験問題です。

(V, E) のどの条件の下で、(Extract-Min 操作と Decrease-Key 操作の両方の対数時間実装を使用して) ヒープではなく配列 (頂点によってインデックス付けされる) を使用して Prim のアルゴリズムの最小優先度キューを実装する必要がありますか? )?

(V, E) のどの条件の下で、順序付けられた配列を使用して Prim のアルゴリズムの最小優先度キューを実装する必要がありますか?

プリムのアルゴリズムを使用して最小スパニング ツリーを作成しようとしていますが、実際のヒープについて大きな疑問があります。グラフの隣接リストを頂点のベクトルになるように構成し、各頂点にはエッジのベクトルがあります。エッジには、重み、接続頂点、およびキーが含まれます。ヒープが頂点のヒープであるかエッジのヒープであるかがわかりません。頂点のヒープにすると、重みが同じ親頂点と宛先頂点からのものかどうかを判断する方法がありません。これにより、エッジの頂点リストごとにヒープを作成する必要があると思います。最後の質問は、エッジのヒープまたは頂点のヒープを作成する必要があるかどうかです。エッジのリストの場合、エッジの重みをキーとして使用する必要がありますか、それとも優先キューに実際に使用できるキーと呼ばれる別のデータ メンバーを使用する必要がありますか? ありがとう！

min-heap ベースのプライオリティ キューを使用して Prim のアルゴリズムを実装する必要があります。グラフに頂点 A、B、C、および D が含まれており、undirected隣接リストが以下の場合... [(頂点名、隣接する頂点への重み) としてソートされます]

ラフグラフ:

優先キューはどのようになりますか? 何を入れたらいいのかわからない。全部入れるべき？ABC と D だけを入力する必要があります。手がかりがありません。答えを本当に知りたいです。