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

Pythonの基本

2022.10.28

MSTは、様々な分野で最適経路の算出に広く利用されています。郵便局では、ある地域を配達する郵便配達員の最適な経路を計算し、大規模な通信会社では、通信ケーブルを敷設するための最も安い経路を見つけるなど、さまざまな分野で利用されています。

計算機性能の向上により、グラフをより簡単に操作できるようになった。データ構造とアルゴリズムの研究は、長年に渡って偉大な頭脳によって生み出されたアルゴリズムのおかげで、グラフの利用についてより良い洞察を得ることができた。

そのアルゴリズムの一つがプリムのアルゴリズムである。このアルゴリズムは1930年にVojtech Jarnikによって設計され、その後1957年にRobert C. Primによって再設計された。このアルゴリズムは、重み付き無向グラフの最小スパニングツリーを求めるために使用されます。

このレッスンでは、PythonでPrimのアルゴリズムを実装する方法を学びます。アルゴリズムで使用されるステップをカバーし、関数例を通して実装します。その前に、アルゴリズムそのものを実装する前に理解する必要がある概念の定義に飛び込みます – 木、グラフ、隣接行列、最小スパニングツリーです。

最小スパニング）木とは何か？

木はグラフの一種であるが、すべてのグラフが木であるわけではない。木は他のグラフと異なり、グラフ内にサイクルが存在しない無循環グラフである。

また、木は無向性であり、ノード間に従わなければならない厳密な方向性は存在しない。次の図は、木がどのようなものかを直感的に理解するのに役立つだろう。

左のグラフは木で、右のグラフはサイクルがあるため木ではありません。これは、公園で見慣れた木とはあまり似ていないかもしれませんが、多くの木は実際に木に似ていて、根元のノードから多くの枝や葉を持つ階層構造を持っています。しかし、公平を期すために、コンピュータサイエンスにおけるほとんどの木は、根を頂点とする上下逆さまになっています。

最小スパニングツリー（MST）を見つけることは、現実の世界でもよくあることだ。MSTは、ある地域を「最も安く」カバーする地域を見つけたいときに便利です。例えば、ピザレストランのチェーン店では、保証時間内に最大の配達エリアをカバーし、最小限の店舗数で、最大数の人々にサービスを提供し、結果として最大のリターンを得るには、どこに店舗を出店すればよいかを知りたい場合があります。その結果、レストランの最小スパニングツリーが形成される。

このアナロジーは、宅配ネットワーク、通信ネットワーク、電力網、水道網など、あらゆるインフラストラクチャー・ネットワークに応用できる。

(/assets/images/icon-information-circle-solid.svg)

注：ピザ屋の例では、通りを横断するのにかかる時間がその重みになります。したがって、目標は、都市の中で、すべてのノード（配達エリア／家）を循環（非効率）させずに接続し、すべての重みの合計が最も小さくなるような木を作ることです。実際には，道の「重み」は動的なものなので，決定するのは難しいが，近似値を置くことで，ほとんどの場合，木が正しいことを確認することができる．

エッジに重みが割り当てられているすべての無向グラフについて、最小木（minimum spanning tree）を計算することができる。これらの木はそれぞれ以下の条件をすべて満たしている。

部分グラフである（これは、MSTが元のグラフの一部またはすべての関係を含み、それ以上でないことを意味する）。
木であること（これはサイクルがないことを意味する
MSTの重み（重みの合計）は、グラフ内の異なる潜在的なスパニングツリーの可能な最小の重みである。

スパニングツリー（最大または最小）は、一般的なグラフのすべてのノードを接続するが、必ずしもグラフのすべてのエッジを接続する必要はない-コストを削減するために避けるものもあるし、そうでなくても、すべてのエッジを使うと、パスが循環するものに変わってしまうかもしれない、これではツリーの意味がない。

隣接行列とは？

Primのアルゴリズムを実装する前に理解しておくべきもう1つの概念は、グラフを表現するためのデータ構造である。グラフの関係は様々な方法で表現することができますが、Primのアルゴリズムを実装する際に特に興味深いのが隣接行列です。

この構造は、どのノードがどのノードに接続しているかを示しており、グラフのエッジ構造を表していることになる。隣接行列は、次元n×nの正方行列であり、nはグラフのノード数である。行列の構造が定義されると、そのフィールドで、どのノードが他のノードに接続する経路を持つかが定義される。

以下は、隣接行列として表現された木の例である。

木の各ノードには文字でラベルをつけた。また、隣接行列の各行と各列を1ノードずつラベル付けしました。したがって、隣接行列の各フィールドは2つのノードに対応する。例えば、木がノード A と B の間にエッジを持っている場合、隣接行列のフィールド [A][B] には 1 が付けられる。一方、これらのノード間にエッジがない場合、フィールド [A][B] は 0 でマークされる。

注意：重みのあるグラフを扱う場合、関係があるときは、フィールドに 1 の代わりにエッジの重みを記入することができます。

例の木をもう一度見てみると、それが有向性でないこと、つまり、それぞれのエッジを両方向からトラバースできることに気がつくと思います。隣接行列は、ノード A と B の間にエッジがあるとき、 [A][B] と [B][A] の両方にマークを付けることでそれを表現しています。

隣接行列の読み方

隣接行列のフィールド [A][B] が数字 10 で埋め尽くされている場合、以下のように読みます。グラフには、ノード A と B を結ぶ辺がある。その辺の重みは 10 である。

だから、木の隣接行列は対称行列になるのです。上の図で印をつけた対角線が、行列を上下の三角形と呼ばれる鏡像の2つのセクションに分割しているのがわかると思います。

以上で、プリムのアルゴリズムの概要に入ることができます。

プリムのアルゴリズム直感

1957年、Robert C. Primは、パスの重みを用いてグラフの最小スパニング木を求める一連の手順を設計（というか再設計）した。そのアルゴリズムは次のようなものである．

ランダムなノードを1つ選択する．
1. 選択したノードに接続する重みが最小の経路を選択する。
1. そのパスが新しいノードにつながるので、そこに自分を配置する。
1. 最初の木を形成/更新したら、木全体に接続する最小重量のパスを選択する。サイクルを作らないように留意してください。
1. 手順 3 と 4 を、すべての頂点をカバーするまで繰り返す。

例のグラフを見て、プリムのアルゴリズムを用いて最小木（minimum spanning tree）を求めてみよう。このグラフは、グラフのMSTを求める他の2つのアルゴリズム（クラスカルのアルゴリズムとボルエブカのアルゴリズム）に関するレッスンで使用したものと同じものである。

まず、アルゴリズムを開始するために、ランダムなノードを選択する必要があります。この例では、ノード A から開始することを選択したとする。

開始ノードを選んだら、そのノードに接続する全てのエッジを見る。この場合、ABとACの2つのエッジがあります。そして、重みの小さい方、つまりABを選び、結果の木に加えようとする。もしサイクルを形成していたら、それをスキップして、2番目に重みの小さいエッジを選択する、といった具合です。

この場合、エッジABはサイクルを形成しないので、結果木に追加することができます。

さて、ノード A と B 、そしてその2つのノードを結ぶエッジからなる木ができました。ここでも、今まで作った木のノードに接続されているエッジをすべて見てみる必要があります。その中で最も重みが小さいのは、エッジ AC です。これはサイクルを作らないので、木に追加することができます。

その後、新たに追加するエッジを選ぶ、という流れになります。数回繰り返した後に起こるこの興味深い状況を見てみよう。

結果としての木に接続されているすべての辺を見ると、重みが最小のものは EH であることがわかります。しかし、それを結果木に追加しようとすると、サイクルを形成していることがわかります。したがって、それをスキップして、2番目に重みの小さい辺である DG を選択しなければなりません。

このアルゴリズムをさらに数回繰り返すと、結果としてグラフの最小木が得られます。

この過程は、アニメーションで見ることができます。

Pythonでプリムのアルゴリズムを実装する方法

この章では、グラフのノードに文字ではなく数字でラベルを付けることにします。これにより、アルゴリズムをより簡単に実装することができます。

Primのアルゴリズムを実装するために最初に必要なのは、Graphクラスである。これはグラフを表現するために使うPythonのクラスで、グラフを操作するための関連するメソッドをすべて備えています。この記事では、その簡単な実装を使い、Primのアルゴリズムに適合するように少し変更します。

class Graph:
    def __init__(self, num_of_nodes):
        self.m_num_of_nodes = num_of_nodes
        # Initialize the adjacency matrix with zeros
        self.m_graph = [[0 for column in range(num_of_nodes)] 
                    for row in range(num_of_nodes)]


def add_edge(self, node1, node2, weight):
        self.m_graph[node1][node2] = weight
        self.m_graph[node2][node1] = weight

このクラスには、コンストラクタとグラフに辺を追加するメソッドがあります。この例では、グラフのノード数とグラフそのものを表す隣接行列を格納するために、汎用コンストラクタに手を加えました。呼び出されると、コンストラクタは隣接行列を初期化し、すべての要素をゼロに設定します。

注意: __init__ メソッドでは、リスト内包を利用して隣接行列を初期化しています。ここでは、他のリストでいっぱいの 1 つのリストを作成しました。すべての行は別のリストであり、そこに重みの値を格納しています。

add_edge()メソッドは、隣接行列に辺を追加します。プリムのアルゴリズムは無向グラフを扱うので、add_edge()` は結果として得られる行列が左右対称であることを保証します。

注意：無向グラフの隣接行列の有用な属性の1つは、それが対称的であることです。これは、上半分（グラフの対角線上）が下半分の鏡であることを意味します。このことは、繰り返される値があるため、行列全体を埋める必要がないことを意味します。

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

Graphクラスの内部でprims_mst()` メソッドを定義することができるようになりました。このメソッドを用いて、Primのアルゴリズムのすべてのステップを定義し、その結果としてMSTを生成します。

重みを比較して開始ノードの最小値を探すので、最初のノードがMSTに割り当てられる前に一時的な最小値として機能する数を定義する必要があります。この数値が無限大のように途方もなく大きいと、最初に見つけたノードの重みがそれより小さく、それが選択されることを保証するのに役立ちます。このため、対策として positive_inf を定義します。ただし、この例では数値が10未満であることが保証されているので、一時的に 10 に設定しても技術的に有効です。

どのノードがMSTに含まれるかを識別するために、選択されたノードを追跡する必要があります。すべてのノードがサブグラフの一部となれば、MSTの検索をやめることができます。これを実現するために、ブール値を持つ別の内包リスト、selected_nodesを作成します。この新しい内包リストの各列はノードを表しています。もしノードが MST の一部として選択されていれば、フィールドは True になり、そうでなければ False になります。

resultには、プリムのアルゴリズムの結果である最小スパニングツリーが格納される。これらはすべて、アルゴリズムのメインセクションであるwhile(False in selected_nodes)` ループに集約されます。このループでは、まだ選択されていないすべてのノードに対してループ処理を行います。

この目的のためのMSTは、実際には開始と終了を持ちません。しかし、アルゴリズム的には start と end ノードを持つことが助けになります。startはランダムに選択される最初のノードで、end` は MST に追加する最後のノードです。これらの変数は接続されるノードとして機能し、私たちはそれらを使ってMST行列を埋めていくことになります。

def prims_mst(self):
    # Defining a really big number, that'll always be the highest weight in comparisons
    postitive_inf = float('inf')


# This is a list showing which nodes are already selected 
    # so we don't pick the same node twice and we can actually know when stop looking
    selected_nodes = [False for node in range(self.m_num_of_nodes)]


# Matrix of the resulting MST
    result = [[0 for column in range(self.m_num_of_nodes)] 
                for row in range(self.m_num_of_nodes)]

    indx = 0
    for i in range(self.m_num_of_nodes):
        print(self.m_graph[i])

    print(selected_nodes)


# While there are nodes that are not included in the MST, keep looking:
    while(False in selected_nodes):
        # We use the big number we created before as the possible minimum weight
        minimum = postitive_inf


# The starting node
        start = 0


# The ending node
        end = 0


for i in range(self.m_num_of_nodes):
            # If the node is part of the MST, look its relationships
            if selected_nodes[i]:
                for j in range(self.m_num_of_nodes):
                    # If the analyzed node have a path to the ending node AND its not included in the MST (to avoid cycles)
                    if (not selected_nodes[j] and self.m_graph[i][j]&gt;0):  
                        # If the weight path analized is less than the minimum of the MST
                        if self.m_graph[i][j] &lt; minimum:
                            # Defines the new minimum weight, the starting vertex and the ending vertex
                            minimum = self.m_graph[i][j]
                            start, end = i, j

        # Since we added the ending vertex to the MST, it's already selected:
        selected_nodes[end] = True


# Filling the MST Adjacency Matrix fields:
        result[start][end] = minimum

        if minimum == postitive_inf:
            result[start][end] = 0


print("(%d.) %d - %d: %d" % (indx, start, end, result[start][end]))
        indx += 1

        result[end][start] = result[start][end]


# Print the resulting MST
    # for node1, node2, weight in result:
    for i in range(len(result)):
        for j in range(0+i, len(result)):
            if result[i][j] != 0:
                print("%d - %d: %d" % (i, j, result[i][j]))

ここでは、2つのループを使って、初期グラフの隣接行列を移動しています。最初のループはX軸（行）に対して、2番目のループはY軸（列）に対してです。2番目のループに入る前に、最初のループで与えられたノードが選択されていることを確認する必要がある。これは、それがMSTグラフの一部であることを保証するものである。この処理は、上のコードの if selected_nodes[i]: ブロックで行います。

ツリーの構築を開始すると、最初はどのノードも選択されておらず、すべて False になっているので、最初のループは2番目のループに入る前に終了してしまいます。このため、start と end には初期値として 0 がセットされ、ループから抜けると end の位置に割り当てられたブール値が True になります。その結果、resultの1つのフィールドは既存の最小値で埋められ、resultは左右対称なので、同じトリックを使って self.m_graph で別のフィールドを埋めることができます。

さて、選択ノードができたところで、プリムのアルゴリズムのステップ1ですが、2番目のループの中でステップ2に進みます。まず、各列を移動して、選択したノードと他のノードの関係を調べます。選択したノードは、以下のパラメータに従って、他のn個のノードと比較される。

iで指定された頂点は、頂点jと接続する経路を持っていなければなりません（これは、隣接行列の(i,j)` 位置の重みが 0 より大きくなければならないことを意味します）。
頂点 j が選択されていないこと（すでに選択されている場合は、サイクルになる可能性があります）。

この2つの条件があれば，与えられた関係の辺の重みを，MSTの一般的な最小値と比較することができる．もし重みが最小値より小さければ、それが新しい最小値となり、変数 start と end には i と j の値が入ります。重みが最小値よりも大きい場合は、残りの列を検索し続ける。

startとend` が MST 行列に入力され、探している木が作成されます。その後、初期グラフからすべてのノードを選択するまで、この処理を繰り返します。

グラフの例でプリムのアルゴリズムを試す

先に説明したPrimのアルゴリズムの実装をテストするために、9つのノードを持つ Graph インスタンスを作成しよう。

# Example graph has 9 nodes
example_graph = Graph(9)

そして、先ほどのイラストやアニメーションで使用した例のグラフを再現してみましょう。

example_graph.add_edge(0, 1, 4)
example_graph.add_edge(0, 2, 7)
example_graph.add_edge(1, 2, 11)
example_graph.add_edge(1, 3, 9)
example_graph.add_edge(1, 5, 20)
example_graph.add_edge(2, 5, 1)
example_graph.add_edge(3, 6, 6)
example_graph.add_edge(3, 4, 2)
example_graph.add_edge(4, 6, 10)
example_graph.add_edge(4, 8, 15)
example_graph.add_edge(4, 7, 5)
example_graph.add_edge(4, 5, 1)
example_graph.add_edge(5, 7, 3)
example_graph.add_edge(6, 8, 5)
example_graph.add_edge(7, 8, 12)

そして最後に、アルゴリズムを実行する。

example_graph.prims_mst()

そうすると、次のように出力されます。

0 - 1: 4
0 - 2: 7
2 - 5: 1
3 - 4: 2
3 - 6: 6
4 - 5: 1
5 - 7: 3
6 - 8: 5

これで完成です。プリムのアルゴリズムの直感」で説明したグラフのMSTと同じものです。出力の各行は、「ノード1 – ノード2: 重み」という形でMSTの1つのエッジを表しています。

ランダムなノードから始めることができ、必ずしも最初のノードから始める必要はないことに注意。もし挑戦したいのなら、このコードを修正して、乱数（もちろん正しい範囲内の）を開始ノードとして取り、アルゴリズムが同じ木を別の順序で見つけるのを観察することができる。

プリムのアルゴリズムの複雑さとは？

Prim のアルゴリズムを隣接行列のみで実装した場合、その計算量は O(N²) – ただし N はグラフのノード数です。この場合、単純な実装のため、高い時間計算量が得られます。

隣接行列と一緒にフィボナッチやバイナリヒープを使うような、より複雑な実装を選ぶことで、時間計算量を改善することができます。その場合、時間計算量は O(E log N) となり、PrimのアルゴリズムはKruskalやBorůvkaのアルゴリズムと同程度に高速に実行できることを意味する!

注：Eは初期グラフの辺の数

結論

Primのアルゴリズムは、グラフの最小スパニング木を求める際に、効率的なだけでなく柔軟性があります。また、Pythonの実装は非常にシンプルです。MSTは様々な分野で応用できる便利な構造であり、Primのアルゴリズムは非常に重要なものである。