問題タブ [minimum-spanning-tree]

私の質問が話すように、プリムのアルゴリズムで優先キューを使用する理由を知りたいですか? 単純な方法を使用することからどのように私たちを救うのですか (はい、聞いたことがありますが、理由はわかりません)。

adjacency list について順を追って説明できる人がいれば、とてもうれしいです。コーメンの本を使用しています。

疑似コード:

std::vector を使用してから std::make_heap(); を使用することを考えています。エッジを格納するための優先キューとして。

質問「エッジ-重みの関連付け」とタマスの答えに関連して、元のベクトルの重みから抽出されたmstツリーの弧の重みを取得するために以下のコードを書きました。igraph 0.6 に移行する間、このコードを使用します。

どちらも一般的な igraph の使用と同様に、コードに間違いや改善が見られる場合があります。

ありがとう、ギレルモ。コード：

宿題に次の問題があります。

O（n + m）アルゴリズムを与えて、エッジeがグラフのMSTの一部であるかどうかを確認します

（この割り当てについて他の人から助けを得ることが許可されているので、これは不正行為ではありません。）

BFSを実行して、このエッジが2つのレイヤー間のエッジであるかどうか、もしそうであれば、このエッジがこれらのレイヤー全体で最小であるかどうかを確認できると思います。しかし、このエッジがBFSツリーのツリーエッジではない場合、私は何を言うことができますか？

Adaの Kruskal のアルゴリズムを参照すると、どこから始めればよいかわかりません。

実際にプログラムを書く前に、すべてを考えようとしていますが、どのデータ構造を使用すべきか、すべてをどのように表現するかについてかなり迷っています。

私の当初の考えは、隣接リストで完全なツリーを表すことでしたが、ウィキペディアを読むと、アルゴリズムは次のように述べられてcreate a forest F (a set of trees), where each vertex in the graph is a separate treeおり、非常に面倒にならずにこれを実装する方法がわかりません。

次にやるべきことは ですがcreate a set S containing all the edges in the graph、繰り返しになりますが、これを行う最善の方法が何であるかはわかりません。to、 、fromを含むレコードの配列を考えていましたが、 .weightで迷ってしまいましたforest。

最後に、エッジが 2 つのツリーを接続しているかどうかを知る方法を見つけようとしていますが、これをすべて行う最善の方法が何であるかはわかりません。

これらすべてのルート頂点間のルート頂点のセットが与えられた有向グラフで最小スパニング ツリー (最適分岐) を計算するアルゴリズムがあるかどうかを知りたいのですが、グラフ内の 1 つのルート頂点と他のすべての頂点だけではありません。 .

ルート頂点のセット [1,4,6] と、次の図のようなグラフ G があるとします。

...アルゴリズムは、同じ画像の緑色のサブグラフのようなものを返す必要があります。

アルゴリズムに提供されたすべてのルート頂点を接続するような MST を取得したいと思います。私は、自称アルゴリズムの結果は、すべてのルート頂点と G の他のいくつかの頂点を含むグラフ G のサブグラフであると考える傾向があります。

ノート：

1. 有向グラフの MST がないことは知っていますが、Chu–Liu/Edmonds アルゴリズムはあります。
2. このようなアルゴリズムの結果 (実際に可能であれば) は、グラフのいくつかの頂点とすべてのルート頂点を含む最適な分岐を返すと思います。

Prim のアルゴリズムを変更して、最大スパニング ツリーを見つけられるようにしたい

コーメンなどの最小全域木について読んでいます。以下は、一般的な最小スパニングツリーです。

重み関数w：E->Rを持つ接続された無向グラフG=（V、E）があり、Gの最小全域木を見つけたいと仮定します。ここでは欲張りアプローチを使用します。この欲張り戦略は、次の「一般的な」アルゴリズムによってキャプチャされます。このアルゴリズムは、最小スパニングツリーを一度に1つのエッジで成長させます。アルゴリズムはエッジAのセットを管理し、次のループ不変条件を維持します。

各反復の前に、Aはいくつかの最小全域木のサブセットです。

質問

1. 「A」が最小全域木のサブセットであるという不変条件でのauthoreの意味は何ですか？この声明の「いくつか」とは何ですか？MSTは1つだけだと教えました。

2. 上記の擬似コードで、作成者は「Aはスパニングツリーではない」とはどういう意味ですか？つまり、whileループがいつどのように終了するのでしょうか。

3. 「いくつかの」最小スパニングツリーがある擬似コードでは、ここでの私の理解は1つだけです。私は正しいですか？

誰かが小さな例で説明できますか？

ありがとう！

重み付き無向グラフ G = (V,E) があるとします。各頂点には要素のリストがあります。

頂点ルートから開始し、値xを持つ要素のすべての出現を探し始めます。値xを持つ要素のすべての出現を明らかにするために、(エッジの重みに関して) 最小量の距離を移動したいと考えています。

私の考えでは、MST にはすべての頂点 (したがって、条件を満たすすべての頂点) が含まれます。したがって、すべてのオカレンスを明らかにするアルゴリズムは、ルートから他のすべての頂点への最短パスを見つけることで実行できます(これはもちろん MST で実行されます)。

編集: ルイが指摘したように、ルートが任意に選択された場合、MST はすべての場合に機能するとは限りません。ただし、明確にするために、ルートは入力の一部であるため、可能な MST は 1 つだけです (エッジの重みが異なる場合)。このスパニング ツリーには、ルートから始まるグラフ内の他のすべての頂点へのすべての最小コスト パスがあります。

サンプルの問題では、重み付きグラフG =（V、E）のMSTTが与えられています。問題は、新しい頂点vとそのすべてのエッジをグラフに追加する場合、この新しいG * =（VU v、 E *）。

これまでの私の唯一のアイデアは次のとおりです。

2つの問題：

1. 切断された可能性のある頂点をどうすればよいですか
2. これは間違いなくO（| V | log | V |）ではありません

これどうやってするの？

最小スパニングツリーアルゴリズムについて読んでいます。カットについて言及されています。無向グラフのカット（S、VS）G =（V、E）は、Vのパーティションです。エッジは、その重みがカットを横切るエッジの最小値である場合、カットを横切るライトエッジです。

上記の定義は、クラスカル法とプリム法でどのように使用されますか？

KruskalsとPrimのアルゴリズムでカットがどのように使用されているのかわかりません

ありがとう