あ 最小スパニングツリー (MST) として定義されます スパニングツリー 考えられるすべてのスパニング ツリーの中で最小の重みを持つもの

ジャワで

あ スパニングツリー は、グラフのすべての頂点を含む、接続された無向グラフのツリー状のサブグラフとして定義されます。平たく言えば、ツリーを形成するグラフのエッジのサブセットです ( 非周期的な ) ここで、グラフのすべてのノードはツリーの一部です。

最小スパニング ツリーには、スパニング ツリーのすべてのプロパティがあり、すべての可能なスパニング ツリーの中で可能な最小の重みを持つという制約が追加されています。スパニング ツリーと同様に、グラフには多数の MST が存在する可能性があります。

スパニングツリーのプロパティ:

スパニングツリーには、 後述の原則 :

• 頂点の数 ( で ) グラフとスパニングツリーは同じです。
• スパニング ツリーには、頂点の総数から 1 を引いた数に等しい固定数のエッジがあります ( そして = V-1 ）。
• スパニングツリーは、 切断された のように、コンポーネントのソースは 1 つだけである必要があり、それ以上ではありません。
• スパニング ツリーは次のようになります。 非環状、 どれの これは、ツリー内にサイクルが存在しないことを意味します。
• スパニング ツリーの総コスト (または重み) は、スパニング ツリーのすべてのエッジのエッジ重みの合計として定義されます。
• グラフには多くのスパニング ツリーが存在する可能性があります。

最小スパニング ツリー:

あ 最小スパニングツリー (MST) として定義されます スパニングツリー 考えられるすべてのスパニング ツリーの中で最小の重みを持つもの。

最小スパニング ツリーには、スパニング ツリーのすべてのプロパティがあり、すべての可能なスパニング ツリーの中で可能な最小の重みを持つという制約が追加されています。スパニング ツリーと同様に、グラフには多数の MST が存在する可能性があります。

• 上の例のグラフの MST を見てみましょう。
  

最小スパニングツリー

最小スパニング ツリーを見つけるアルゴリズム:

特定のグラフから最小スパニング ツリーを見つけるアルゴリズムがいくつかあり、その一部を以下に示します。

Kruskal の最小スパニング ツリー アルゴリズム:

これは、接続された無向グラフから最小スパニング ツリーを見つけるための一般的なアルゴリズムの 1 つです。これは まず、グラフのすべてのエッジを重みでソートします。

このアルゴリズムは、グラフの接続されたコンポーネントを追跡するために DSU ( Disjoint-Set ) データ構造を使用して効率的に実装できます。これは、ネットワーク設計、クラスタリング、データ分析などのさまざまな実用的なアプリケーションで使用されます。

Javaのオブジェクトの配列

の記事に従ってください Kruskal の最小スパニング ツリー アルゴリズム アルゴリズムのより良い理解と実装のために。

Javaでnullをチェックする

このアルゴリズムは、色、テクスチャ、またはその他の特徴に基づく画像のセグメンテーションなど、さまざまなシナリオで使用できます。ルーティングの場合、配送トラックがたどる 2 点間の最短経路を見つける場合など。

の記事に従ってください Prim の最小スパニング ツリー アルゴリズム このアルゴリズムのより良い理解と実装のために。

Boruvka の最小スパニング ツリー アルゴリズム:

これは、接続された無向グラフの最小スパニング ツリーを見つけるために使用されるグラフ トラバーサル アルゴリズムでもあります。これは最も古いアルゴリズムの 1 つです。このアルゴリズムは、グラフ内の各頂点を独自のツリーとして開始して、最小スパニング ツリーを反復的に構築することによって機能します。各反復で、アルゴリズムはツリーを別のツリーに接続する最も安価なエッジを見つけ、そのエッジを最小スパニング ツリーに追加します。これは、最小スパニング ツリーを見つけるための Prim のアルゴリズムにほぼ似ています。このアルゴリズムには次のワークフローがあります。

• グラフ内の各頂点を独自のツリーとして使用して、ツリーのフォレストを初期化します。
• 森の各木について:
  • 別のツリーに接続する最も安価なエッジを見つけます。これらのエッジを最小スパニング ツリーに追加します。
  • 追加したエッジで接続されたツリーを結合してフォレストを更新します。
• フォレストに最小スパニング ツリーであるツリーが 1 つだけ含まれるまで、上記の手順を繰り返します。

このアルゴリズムは、ツリー間の最も安価なエッジを効率的に見つけるために、優先キューなどのデータ構造を使用して実装できます。 Boruvka のアルゴリズムは、最小スパニング ツリーを見つけるためのシンプルで実装が簡単なアルゴリズムですが、多くのエッジを持つ大きなグラフでは他のアルゴリズムほど効率的ではない可能性があります。

の記事に従ってください Boruvka の最小スパニング ツリー アルゴリズム このアルゴリズムのより良い理解と実装のために。

最小スパニング ツリーのプロパティと特性について詳しく知るには、ここをクリックしてください。 ここ。

最小スパニング ツリーのアプリケーション:

• ネットワーク設計 : スパニング ツリーをネットワーク設計で使用すると、すべてのノードを接続するために必要な最小接続数を見つけることができます。特に最小スパニング ツリーでは、最も安価なエッジを選択することで接続コストを最小限に抑えることができます。
• 画像処理 : スパニング ツリーを画像処理で使用すると、同様の強度や色の領域を識別できるため、セグメンテーションや分類のタスクに役立ちます。
• 生物学 : スパニング ツリーとミニマム スパニング ツリーは、生物学において種または遺伝子間の進化的関係を表す系統樹を構築するために使用できます。
• ソーシャルネットワーク分析 : スパニング ツリーとミニマム スパニング ツリーは、ソーシャル ネットワーク分析で個人またはグループ間の重要なつながりや関係を特定するために使用できます。

MST で人気のある面接の問題

最小スパニング ツリーに関するよくある質問:

1. 特定のグラフに複数の最小範囲ツリーが存在できますか?

はい、同じ最小合計重みを持つエッジのセットが複数ある場合、グラフに複数の最小スパニング ツリーを含めることができます。

一年を四半期に分けて

2. Kruskal のアルゴリズムと Prim のアルゴリズムは有向グラフに使用できますか?

いいえ、Kruskal のアルゴリズムと Prim のアルゴリズムは、無向グラフ専用に設計されています。

3. 切断されたグラフに最小スパニング ツリーを含めることはできますか?

いいえ、切断されたグラフはすべての頂点にまたがらないため、スパニング ツリーを持つことはできません。したがって、最小スパニング ツリーを持つこともできません。

4. ダイクストラのアルゴリズムを使用して最小スパニング ツリーを見つけることができますか?

いいえ、ダイクストラのアルゴリズムは、重み付きグラフ内の 2 つの頂点間の最短経路を見つけるために使用されます。最小スパニング ツリーを見つけるように設計されていません。

5. クラスカルとプリムのアルゴリズムの時間計算量はどれくらいですか?

Kruskal と Prim の両方のアルゴリズムの時間計算量は次のとおりです。 O(エログE) ここで、E はグラフ内のエッジの数です。