プリム法とは？アルゴリズムやPythonの実装まで解説！

サル

• プリム法って何？
• プリム法はどうやって解いたらいいの？
• プリム法をPythonで実装するには？

こんな悩みを解決できる記事になっています！

なぜなら、僕が大学でプリム法を勉強して、分からなかった部分を噛み砕いて説明するためです。

本記事の信頼性

プリム法は以下のようなステップで最小全域木を求める手法になります。

• スタートとなる点を選ぶ
• その点に繋がっている最小の辺を選ぶ
• さらに他の点と繋がっている最小の辺を追加する
• すべての点と繋がれば終了

この記事を読み終えることで、プリム法を解けるだけでなく、人に分かりやすく説明できるようになるでしょう。

記事の前半では『プリム法のアルゴリズム』を紹介し、記事の後半では『プリム法のPythonでの実装』を具体的に解説します。

「問題の解き方を早く知りたい！」という方は、『プリム法のアルゴリズム』にジャンプしてください！

月額980円で学べる！

しょー

データサイエンスの復習は完ぺきにできていますか？

データサイエンスは勉強する範囲が膨大で、復習に手が回りませんよね。

そんなあなたにおすすめなのが、たった月額980円でサクッと学べる『スタアカ』

数分の動画でビジネスへの活用法も含めて、サクッとデータサイエンスを復習可能。

『何冊も参考書を往復して復習する苦労』とはおさらばです！

サブスクなのでいつでも解約OK。手軽に始めてみませんか？

＼月額980円から／

スタアカはこちら

講座が毎月追加されるので今後値上がりする可能性大、今買わなきゃ損するかも！

しょー

それでは本編です！

プリム法とは

プリム法は頂点と辺で構成される図（グラフ）において、それぞれの点を最も安いコスト（費用）でつなぐ方法を見つける手法です。

そして、その時々で最もコストがかからない選択をしていく「貪欲法」で最小全域木を求めていきます。

例えば、いくつかの町が点であって、できるだけ安く道路を繋ぎたい時に、どう道路を作ればいいかを計算できるのです。

上の画像のように、ある町から最小のコストで道路を繋げられるのが「プリム法」の特徴になります。

しょー

それでは、アルゴリズムの解説に移ります！

プリム法のアルゴリズム

プリム法のアルゴリズムはある点から最小のコストを調べていく「貪欲法」になります。

具体的には、以下の手順がおおまかなアルゴリズムです。

• スタートとなる点を選ぶ
• その点に繋がっている最小の辺を選ぶ
• さらに他の点と繋がっている最小の辺を追加する
• すべての点と繋がれば終了

この記事では、以上の手順を具体例を用いて説明していきます。

具体例となる問題は以下の図の通りです。

それぞれ解説していきます。

STEP1. スタートとなる点を選ぶ

まずプリム法では、グラフの中から任意の点（どれか1つの点）を選び、最小全域木の出発点とします。

どの点を選んでも、最終的な最小全域木には影響しませんので、どこから始めても大丈夫です。

それでは、例題から出発点（最小全域木のスタート点）を設定ます。

今回は町Aから始めてみますが、どの町から始めても最小全域木は変わりませんので、安心してください。

そして、町A以外の「町B・町C・町D・町E・町F」はこれから探索する点として覚えておきましょう。

しょー

次のステップで最小の辺を繋いでみます！

STEP2. その点に繋がっている最小の辺を選ぶ

出発点が定まれば、その出発点に繋がっている辺の中から、最小の重み（コスト）の辺を選びます。

最小の重みの辺を選ぶことで、自動的にもう1つの点と出発点を繋げられるのです。

それでは、例題から最小の重みの辺を選びましょう。

上の図から、町Aに繋がっている辺は、町Bと町Cに繋がっており、

• 町Aから町Bへのコスト：2
• 町Aから町Cへのコスト：1

の状態だと分かりますよね。

この場合、最小の重みの辺は町Aと町Cを繋ぐ辺なので、この辺を最小全域木の一部として選びます。

そして、これから探索したい点を「町B・町D・町E・町F」に更新してください。

STEP3. さらに他の点と繋がっている最小の辺を追加する

STEP3では、STEP2で選ばれた辺から新たに繋がった点から、再び最も小さい重みを持つ辺を探します。

この時、すでに最小全域木に含まれている頂点への辺は選ばないように探索したい点のリストを参照してください。

最小の重みの辺を求める手順を繰り返すことで、少しずつ最小全域木が求まってきます。

それでは、例題から確認してみましょう。

STEP3では、町Aと町Cから出ている線の中で、すでに選んだ町Aへの線は除外して最もコストが低いものを探します。

このように、1つずつ確実に最小の重みの辺を選んでいくのが「貪欲法」です。

プリム法の根幹部分のSTEPですので、必ず抑えておくようにしましょう。

STEP4. すべての点と繋がれば終了

STEP3でやったことををすべての点が最小全域木に含まれるまで続けます。

最終的に、すべての頂点が最小のコストで繋がれば終了とし、求めたかった最小全域木が完成です。

例題で、STEP3をすべての点に対して繰り返すと以下のような最小全域木になります。

上の図のように、すべての町が繋がれば、その時点で最もコストが低い道路の組み合わせが完成します。

このように、プリム法は任意の点（どんな点）からでも最小全域木が求められるアルゴリズムです。

なので、ぜひ他の点から始めて同じ最小全域木になるか確かめてみてください。

プリム法をPythonで実装する

プリム法はPythonというプログラミング言語を用いると、簡単に実行できます。

今回は、町の道路の最小全域木の例でそれぞれのコストを変更した例でプリム法を行います。

以下が簡単なコード例です。

import heapq

def prim(graph, start):
    # すでにつないだ町を覚えておくためのメモ
    visited = set([start])
    # スタート地点から出ている辺をリストアップ
    edges = [(cost, start, to) for to, cost in graph[start].items()]
    heapq.heapify(edges)  # このリストを優先度付きキュー（重要なものから順に取り出せるリスト）に変換
    # 最終的な道路のリスト
    mst = []

    while edges:
        cost, frm, to = heapq.heappop(edges)  # 一番コストが低い辺を取り出す
        if to not in visited:
            visited.add(to)  # 新しくつないだ町をメモに追加
            mst.append((frm, to, cost))  # 道路のリストに追加
            # 新しくつないだ町から出ている辺をリストに追加
            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst  # できた道路のリストを返す

# 例としての町と道路のコストを定義
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
    'C': {'A': 3, 'B': 1, 'F': 5},
    'D': {'B': 1, 'E': 1},
    'E': {'B': 4, 'D': 1, 'F': 1},
    'F': {'C': 5, 'E': 1}
}

# プログラムを実行して、どの道を作ればいいかを計算する
mst = prim(graph, 'A')
print(mst)  # 計算結果を表示する

町と町をつなぐ道のコストをリストにして、プリム法に従って最も安い道路の組み合わせを探しています。

上のコードでは、町Aから始めて、最終的にどの道を選べばいいかを計算していて、実行するとそれぞれの辺が出力されます。

しょー

グラフの重みを変えて、実行してみると答えが変わるので面白いですよ！

まとめ

プリム法とは頂点と辺で構成される図（グラフ）において、それぞれの点を最も安いコスト（費用）で繋ぐ手法です。

プリム法のアルゴリズムは以下の4ステップで行うとよいでしょう。

• スタートとなる点を選ぶ
• その点に繋がっている最小の辺を選ぶ
• さらに他の点と繋がっている最小の辺を追加する
• すべての点と繋がれば終了

プリム法のPythonでの実装も、アルゴリズムがもとになっています。

なので、アルゴリズムの理解もできるだけ併せて行うようにしましょう！

しょー

1度あなた自身で順を追ってみると分かりやすいですよ

あなたはいつもどこかで、

「データサイエンスの勉強がなかなか上手く進まない...」
「勉強しても全体像が見えてこない...」
「本当にデータサイエンティストになれるのかな...」

と不安に感じてはいませんか？

僕も勉強しながら同じような悩みを常に持っていました。

ですが、そんな僕の悩みをまるっと解決してくれたサービスが『スタアカ』です。

サル

データサイエンスを学べるサービスなんて高額なんでしょ？

データサイエンスを学ぶためにもう高額なお金を払う必要はありません。

僕が利用している『スタアカ』のライトプランは月額980円で動画見放題のコスパ最強サブスクです。

「ちょっと興味がある」という方は、受講した感想も載せている記事をご覧ください。

たった月1000円で、もう二度と独学で悩まずに済みます。

正直、「就職・転職までサポートしてほしい」という方にはおすすめできません。

ですが、「勉強の道しるべが欲しい！」「学習を効率的に進めたい」という方にはこの上ないサブスクです。

データサイエンスを学びたい方に最強のサブスク『スタアカ』を気軽に始めてみませんか？

＼月額たった980円！／

スタアカはこちら

講座が毎月追加されるので今後値上がりする可能性大、今が買いどき！