1. 序章

このチュートリアルでは、無向グラフを使用して、プリムのアルゴリズムを使用して最小全域木（MST）を抽出します。 これは、コンピュータサイエンスとグラフ理論に不可欠なアルゴリズムです。 グラフ理論で人気のあるアルゴリズムには、 Djikstraの最短経路アルゴリズム、 Kruskalのアルゴリズム、および多くの検索アルゴリズムが含まれます。

2. コンセプト

コンピュータサイエンスには、グラフで最もよく表される現象が数多くあります。 グラフは、エッジ（リンクまたはラインとも呼ばれます）を介して接続されたさまざまなノード（頂点またはポイントとも呼ばれます）のモデルと見なすことができます。

ノード間の方向を指定しないこれらのサブセットは、「無向グラフ」と呼ばれます。 さらに、これらの最も一般的な発生の1つは、コンピュータネットワークです。

ただし、これらの遍在する数学的構造についてより広く考える必要があります。言語学および自然言語処理、ロジスティクス、幾何学、神経学、社会学、化学などの分野におけるそれらの重要性に注意する必要があります。 分子、幾何学的形状、単語間の関係、または輸送ルートをどのように表現するかを考えてください。

その結果、数学者やコンピューター科学者によって徹底的に調査されたグラフには、さまざまな一般的な問題が存在します。

たとえば、これらの問題の1つは、グラフ内のすべてのノードに到達するための最短経路を見つけることです。 このパスは「最小スパニングツリー」と呼ばれます。  したがって、さまざまなアルゴリズムがこのパスを見つける目的を持っており、最も一般的に使用されるものの1つはプリム法です。 これは、無向グラフ全体の最小スパニングツリーを決定する欲張り法です。 「貪欲」という言葉は、問題の最適な解決策を見つけるためにすべてのステップで最良の選択を行うアルゴリズムを示していることに注意してください。

3. 実装

このアルゴリズムは、3つの主要なステップで実装でき、次に分解します。

  1. グラフ内の任意の頂点を選択します。これがツリーの開始点になります。
  2. まだツリーに含まれていないが、ツリーのノードに接続しているすべてのエッジを反復処理し、最小のエッジを選択します。この最小ウェイトのエッジをツリーに追加します。
  3. ツリーにすべてのノードが含まれているかどうかを確認します。含まれていない場合は、手順2を繰り返します。

最適なノードを選択するため、このアルゴリズムは貪欲であると言えます。

さらに、擬似コードを使用して、これをさらに複数のステップに分解できます。

   

 

この手順は、次のアニメーションで視覚化できます。

4. 複雑

特定のグラフのV頂点とEエッジに対するこのアルゴリズムの時間計算量分析は、実装するデータ構造に基づいています。

5. 結論

この記事では、グラフで最小スパニングツリーを見つけるためのプリムのアルゴリズムについて説明しました。