問題タブ [spanning-tree]

赤と青のエッジを持つグラフGと定数Kが与えられた場合、正確にK個の赤のエッジを持つGのスパニング ツリーを見つける決定論的線形時間アルゴリズムを考案します (または、そのようなスパニング ツリーが存在しない場合は戻ります)。False

これまでに行ったこと:

すべての赤いエッジの重みを -1 にし、すべての青いエッジの重みを 0 にします。

最小スパニング ツリーを見つけます (標準の線形時間アルゴリズムを使用)。したがって、重みが最小のスパニング ツリーTがあります。つまり、赤いエッジは重みを減らすだけなので、できるだけ多くの赤いエッジを使用しました。

Tの赤いエッジがK未満の場合、 を返します。False

ちょうどK個の赤のエッジがある場合、完了です。Tが答えです。

K個以上の赤のエッジがある場合、それらを青のエッジに置き換える必要があります。

これが私たちの問題です。線形時間でそれを行うにはどうすればよいでしょうか?

青いエッジが追加されるたびにサイクルが作成されるため、サイクルから赤いエッジを 1 つ削除すると機能しますが、この方法で線形性を確保するにはどうすればよいでしょうか? これも良いアプローチですか？

指定されたグラフが実際にスパニング ツリーであることがわかっている場合、つまり頂点の各ペアにはそれらの間のパスが 1 つしかないことがわかっている場合、すべての頂点からすべての頂点への最短パスを見つけるにはどうすればよいですか? 最適解が欲しい。ダイクストラのアルゴリズムは知っていますが、非常に複雑です。

基本的に、1 つのソースからのすべての頂点の距離とパスを知りたいです。これがスパニング ツリーであることを考えると、これに対する最善かつ最適なソリューションは何ですか?

さらに、グラフが実際にスパニングツリーであることを考慮して、単一ソースの最短パスのアルゴリズムを複数回適用する以外に、すべてのペアの最短パスを見つける別の方法があるかどうかを教えてください。

親切に、過剰な説明を気にしてください。

非有向グラフ (G,V) からスパニング ツリーを作成するために、この疑似コードを書きました。ここで、S はスタック、v は計算を開始する頂点です。

何らかの理由で、このアルゴリズムは間違っています。たとえば、次の単純な無向グラフを考えてみましょう。

最初の頂点から開始する場合は、そこにアクセスし、2 と 3 をスタックにプッシュして、(1,2) と (1,3) の 2 つのエッジを作成します。次に 3 を訪問し、まだ訪問していない 2 に接続されているため、エッジ (3,2) も作成しますが、これによりサイクルが作成されるため、計算されたスパニング ツリーはツリーではありません。どこが間違い？O(n) でスパニング ツリーを計算する別の方法がわかりません。

誰かが私が抱えている問題を解決できることを願っています。まず、問題の原因ではないコードをできる限り削除しようとしました。

私の問題は次のとおりです。プログラムを実行すると、約 130 個のノードを持つグラフを作成するまで、すべてが完全に実行されます。130 以上のノードに達すると、プログラムは無限ループで永遠に実行されます。

目的のグラフ密度を得るために、15 で 135 ノードでプログラムを実行してみます。

いくつかのコンテキストを提供するために、私は研究シミュレーションに取り組んでおり、このためにランダムなグラフを作成し、BFS を使用してスパニング ツリーを構築しています。

スパニング ツリーの作成中に問題が発生します。

コードをコピーして貼り付け、javac MMB.java を使用してすべて 1 つのファイルにコンパイルします。

グラフの分散をエッジの重みの分散として定義しましょう。私が解決しようとしているタスクは、与えられたグラフ G が最小分散のスパニング ツリー T を構築するアルゴリズムを設計することです。

これでボールを転がすのに苦労しています。これまでのところ、このようなスパニング ツリーのエッジの平均重みがわかっている場合、すべてのエッジの重みを平均重みの偏差の 2 乗に置き換え、グラフを MST の結果に入力することで問題を解決できることに気付きました。アルゴリズム。

明らかに、構築しようとしているツリーの平均エッジの重みについては何も知りませんが、平均は G の 2 つのエッジの間にある必要があり、おそらくこの情報を利用できる可能性があることに気付きました。

私は修正された辺の重みで G の MST を見つけることに問題を軽減しようとしています。G の各エッジに対してアルゴリズムを実行することを考えました。毎回、最初のエッジが T の平均に最も近く、重み 0 が与えられていると仮定し、他のエッジは最初のエッジの重みからの偏差の 2 乗に等しい重みを取得します。 . 平均がエッジの 1 つの重みと等しくない場合、2 つの最も近いエッジの重みの間のどこにあるかに応じて、重みに基づくエッジの順序が異なり、異なるスパンが生成されるため、このアプローチはどこにも行きませんでした。 MST 発見アルゴリズムに供給されたときのツリー。これは、私が処理する方法がわからないものです (または、処理できるかどうかさえわかりません)。

これは宿題なので、解決策ではなく、正しい方向に導くための小さなヒントが欲しい.

頂点 v から始まるグラフのスパニング ツリーがあります。すべてのエッジは同じ距離です (1 としましょう)。

v から別の頂点 u への最短経路をどのように計算できますか?

少なくとも 500 のウィキペディア ページと、これらのページから他のウィキペディア ページへのリンクを収集するプログラムを作成しました。グラフ内の 2 つの頂点 (Web ページ) 間のコストを決定するために、各 Web ページから単語の頻度を収集します。

私は今、2番目のプログラムを作成しようとしています。Swingを使用して NeatBeans で GUI を作成しています。ユーザーは 2 つの Web ページを選択し、それらの間の最短パスをグラフィカルに表示できます。グラフを視覚的に表示する方法がわかりません。JFreeChartまたはJUNGの使用を検討してきましたが、どちらも希望する種類のグラフを作成できないようです。

これが私が作成しようとしているものの例です:

この質問は次の質問と非常によく似ています:正確に k 色のエッジを持つスパニング ツリー

それは同じ質問ではありません！- ご覧のとおり、上記の質問の答えは (私の Q に対して) 同じではありません。

G=(V,E)それぞれ赤または青のエッジを持つ接続された無向グラフがあります。

私たちはそれを知ってい|V|=nます。2 つの数値を取得します。は赤いエッジ用a1,a2∈Nで、 は青いエッジ用です。.a1a2a1+a2=n−1

a1正確に赤のエッジとa2青のエッジを持つスパニング ツリーがあるかどうかを確認するアルゴリズムを見つける必要があります。そうでない場合、アルゴリズムは、この条件のスパニング ツリーがないことを返します。

上記の質問から助けを得ようとしましたが、まだ立ち往生しています。これらは非常によく似た質問だと思います。

そのため、この課題では、幅優先スパニング ツリーを返すルーチンを EdgeList および AdjMatrix オブジェクト クラスに追加する必要があります。署名は次のようになります。

EdgelList: EdgeList BFSpanning();

AdjMatrix: EdgeList BFSpanning();

しかし、私は本当に混乱しています.BFSpanningメソッドを両方のクラス内に書くだけですか? 誰かが私に難しい構造を教えてくれますか? 私は正しい方法を書くことを思いつかないようです。

これが私のadjmatrixクラスです：

これが私のedglistクラスです：

また、このクラスのエッジを表示する必要があるかどうかもわかりません: