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

Pythonの基本

2022.10.20 2022.09.27

クラスカルのアルゴリズムは、グラフの最小木（MST）を求めるための3つの最も有名なアルゴリズムのうちの1つである。

クラスカルのアルゴリズムは、小さな局所最適を見つけ、それらを組み合わせることによって全体最適解を求める貪欲なアルゴリズムである。そのほかにも、今でもかなり有用で広く普及している。

このレッスンでは、クラスカルのアルゴリズムがどのように動作するかを実例で説明し、その後、Pythonでの詳細な実装をお伝えします。

Pythonでのグラフに関する話題はすでにたくさん取り上げてきました。もし、特定のトピックやアルゴリズムについてもっと学びたいと思ったら、ぜひいくつか読んでみてください。

注意：このレッスンでは、グラフのMSTを求めるクラスカルのアルゴリズムを理解するために必要な概念だけを説明する。

それ以外の概念は「グラフ理論とグラフ関連アルゴリズム」のレッスンで説明していますので、ぜひ事前に読んでおいてください。

最小スパニングツリーとは何ですか？

最小スパニングツリーとは、簡単に言うと、重み付き無向グラフから構成されるツリーのことです。

すべてのノード(頂点)を接続する。
サイクルがない
エッジの重みの和が最小であること

この非公式な定義を検証し、定義された条件についての誤解を解いていこう。

まず重要なことは、MSTは重みつき無向グラフにしか作れないということである。つまり、グラフの各辺には数値の重みが割り当てられており、（有向グラフとは異なり）各辺を両方向からトラバースできる。

MSTは、グラフからすべてのノードを接続する。つまり、グラフ内の他のすべてのノードから、任意の1つのノードにアクセスできなければならない。もちろん、グラフからいくつかのエッジを除外することは可能である。実際、グラフから不要なエッジを除外すると、すべてのエッジの重みの合計が減少し、生成される木がMSTになる確率が高くなる。

MSTは可能な限りエッジの重みの和が小さくなければならない。時には、同じ辺の重みの和を持つ木が複数存在することもある。その合計が最小であれば、そのうちのどれかがMSTになる可能性がある。

最後の事実は、ほとんど自明である。ご存知のように、木は特殊なグラフである。簡単に言えば、サイクルを持たない連結グラフであり、MSTは木の一種であるから、サイクルを持たないと言うことである。

このことは、MSTがサイクルを持たないことを意味している。

重要な性質である。グラフが n 個のノードを持つ場合、各スパニングツリー (MST を含む) は n-1 個のエッジを持つ。

クラスカルのアルゴリズムの説明

プリムやボルエブカと並んで、クラスカのアルゴリズムは、重み付き無向グラフの最小スパニングツリーを求める最も有名なアルゴリズムの1つである。このレッスンでは、Borůvkaのアルゴリズムについて説明したレッスンと同じグラフを使う。

注：このセクションだけ、読みやすくするために、各ノードに番号の代わりにアルファベットをつけた。

クラスカルのアルゴリズムの背後にある考え方は非常に単純で、基本的に2つのステップをMSTが得られるまで繰り返す。

すべてのエッジをその重みの昇順でソートする。
重みが最も小さいエッジを選び、それをツリーに追加してみる。
サイクルを形成している場合は、そのエッジをスキップする。
すべてのノードをカバーする連結木ができるまで、このステップを繰り返す

このグラフの場合、すべてのエッジのソートされたリストは次のようになります。

| エッジ｜ウェイト
| — | — |
| EF | 1
| CF 1
| DE
| FH 3
| AB
| EH 5
| GI
| DG 6
| AC
| BD
| EG 10
| BC 11
| HI｜12号機
| EI
| BF｜20｜です。

エッジ EF と CF は同じ重みを持っているので、どちらかを開始エッジとして選ぶことができます。ここでは、EFを選んだと仮定します。この時点では、MSTを構成するのに使う木は空っぽです。ここで、EF`を木に追加して、サイクルを形成しているかどうかを調べます。

見ての通り、EF`を追加してもサイクルは形成されないので、木に残すことができます。次に、ソートされたリストのすべての辺について、このステップを繰り返します。もちろん、まず重みが最小の辺をチェックし、それを繰り返していきます。

興味深いのは、EHを木に追加しようとするときです。

EHを木に追加すると、サイクル -EFHが生成されます。したがって、EHを木から除外して、次の最小重みの辺 -GIを含めることができるかどうか確認する必要があります。GI を木に追加した後は、すべてのノードが訪問されます。

すべてのノードを訪問しましたが、この木はまだつながっていません。A, B},,` の3つの部分木があることに気がつきます。これらの部分木は、初期グラフのすべてのノードをカバーする最小分散林を形成しますが、MSTではありません。MSTは初期グラフのすべてのノードを接続しなければならないので、森が1つの接続木になるまでエッジを追加し続けなければならない。クラスカルのアルゴリズムは、追加されたエッジが最小限の重さであることを保証する。

注）基本的には、クラスカルのアルゴリズムは、部分木を形成し、最小限の重さのエッジで接続するアルゴリズムであると考えることができる。そうすることで、MSTを作る。

数歩進んで、先ほどの図の森にエッジ「DG」と「AC」を追加すると、その森は連結木になります。実は、これが初期グラフのミニマムスパニングツリーになるのです。

この過程はアニメーションで見るとよくわかります。

クラスカルのアルゴリズムをPythonで実装する方法

この節では、前節と同じグラフを使用します。唯一の違いは、実装を簡単にするために、各ノードに文字ではなく数字（0から始まる）で印をつけることである。

Graph` クラスの実装

最初に実装する必要があるのは Graph クラスです。これはグラフを表すクラスで、グラフを扱うときに必要となるすべてのメソッドを定義しています。

class Graph:
    def __init__(self, num_of_nodes):
        self.m_num_of_nodes = num_of_nodes
        self.m_graph = []


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

これはかなり一般的な Graph クラスの実装ですが、クラスカルのアルゴリズムと互換性を持たせるために、いくつかの微調整が必要でしょう。以下の節で、そのような微調整を紹介します。

すでにご存知のように、Pythonでは __init__ は事実上任意のクラスのコンストラクタです。この例では、Graph(num_of_nodes) を呼び出してグラフを構築します。Graphクラスに格納される値は、グラフのノードの数 (m_num_of_nodes) とエッジの配列 (m_graph`) の2つだけです。この辺の配列は、この例でグラフを格納するために使用するデータ構造です。

重み付きグラフのすべてのエッジは正確に2つのノードを結び、ある重みが割り当てられています。add_edge(node1, node2, weight)メソッドはその性質を表しています。これは、Graphオブジェクトに[node1, node2, weight]` という形でエッジを追加します。これは Python でグラフを表現する最もシンプルで非常に効果的な方法です。

コンストラクタと addEgde() 以外にも、いくつか実装しなければならないメソッドがあります。その方法と理由を理解するために、まず実装の重要な部分を説明し、新しいメソッドを紹介する前に基礎知識を得ておきましょう。では、はじめましょう。

補助配列 – parent と subtree_sizes.

クラスカルのアルゴリズム自体の実装は、かなり簡単なものであるはずだ。ただ、覚えておくべき重要なポイントがいくつかあります。まず、すでにエッジのリスト（前述した方法で表現されている）を持っていると仮定して、エッジの重みが小さいものから大きいものへとソートする必要がある。

その後， parent と subtree_sizes という 2 つの補助配列を初期化し，保持する必要があります．この 2 つの配列の作り方は非常に重要なので、注意深く見ていってください。どちらも、初期グラフのノード数に対応したサイズを持っています (つまり、初期グラフのノード数が n ならば、これら 2 つの配列は n 個の要素を持ちます)。

このように，これらの配列の各インデックスは，グラフのちょうど1つのノードに直接対応します．例えば、 parents[3] と subtree_sizes[3] を呼び出せば、ノード 3 に関するあらゆる情報にアクセスすることができます。

さて、この 2 つの配列の作り方を理解したところで、なぜこの 2 つの配列が必要なのかを説明しましょう。前にも述べたように、クラスカルのアルゴリズムは、効果的に部分木の集合（あるいは森）を作り、それらを可能な限り小さな重さの辺でつなぎます。はじめは、個々のノードを別々の木とみなして、それらをつなげていきます。そして、最初のグラフのすべてのノードをつなぐ1本の木ができるまで、サブツリーをつなげていく。

そこで登場するのが parent 配列です。すでにご存知のように、この配列のインデックスはノードを表します (例えば、インデックス 3 はグラフのノード 3 を表します)。また、 parent 配列には、どのノードがどのサブツリーに属しているかという情報が格納されます。最初は全てのノードを別々のサブツリーとみなすので、 parent 配列は以下のようなものになる。

見ての通り、各ノードはそれ自身の親であり、結果として木は空になります。最小の重みを持つエッジを選んで結果の木に追加すると、実際には開始時のサブツリーのうちの2つを接続することになる。

このグラフの例では、最小の重みを持つエッジは、ノード 5 と 2 を結ぶものであり、これらは両方とも最初のグラフの部分木である。この2つのエッジを接続すると、ノード 2 と 5 を含む、新しい大きなサブツリーが形成されます。parent配列は、ノード2をノード5` の親ノードとして代入することで、これを反映します。

これは、複数のサブツリーではなく、1つのツリーになるまで続けられます。

このように、 parent と subtree_sizes 配列を記述して管理するために、 Graph クラスで以下のメソッドを実装する必要があります。

# Finds the root node of a subtree containing node `i`
def find_subtree(self, parent, i):
    if parent[i] == i:
        return i
    return self.find_subtree(parent, parent[i])


# Connects subtrees containing nodes `x` and `y`
def connect_subtrees(self, parent, subtree_sizes, x, y):
    xroot = self.find_subtree(parent, x)
    yroot = self.find_subtree(parent, y)
    if subtree_sizes[xroot] &lt; subtree_sizes[yroot]:
        parent[xroot] = yroot
    elif subtree_sizes[xroot] &gt; subtree_sizes[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        subtree_sizes[xroot] += 1

find_subtree()メソッドはparent配列を再帰的に検索し、ノードi` を含むサブツリーを見つける。

connect_subtrees()メソッドは、2 つのサブツリーを接続します。1 つのサブツリーはノードxを含み、もう 1 つのサブツリーはノードy` を含む。まず、2つのサブツリーを見つけ、そのサイズを比較し、小さい方のサブツリーを大きい方のサブツリーに接続します。

これで Graph クラスの実装とすべての追加メソッドを説明したので、次はクラスカルのアルゴリズムそのものを実装する方法を見てみよう。

クラスカルのMSTアルゴリズム

Graphクラスの他のすべてのメソッドが説明されたので、クラスカルのアルゴリズムの実装はかなり簡単に理解できるはずです。ここでは、このアルゴリズムをGraph` クラスのメソッドとして実装することにします。

def kruskals_mst(self):
    # Resulting tree
    result = []

    # Iterator
    i = 0
    # Number of edges in MST
    e = 0


# Sort edges by their weight
    self.m_graph = sorted(self.m_graph, key=lambda item: item[2])

    # Auxiliary arrays
    parent = []
    subtree_sizes = []


# Initialize `parent` and `subtree_sizes` arrays
    for node in range(self.m_num_of_nodes):
        parent.append(node)
        subtree_sizes.append(0)


# Important property of MSTs
    # number of egdes in a MST is 
    # equal to (m_num_of_nodes - 1)
    while e &lt; (self.m_num_of_nodes - 1):
        # Pick an edge with the minimal weight
        node1, node2, weight = self.m_graph[i]
        i = i + 1


x = self.find_subtree(parent, node1)
        y = self.find_subtree(parent, node2)


if x != y:
            e = e + 1
            result.append([node1, node2, weight])
            self.connect_subtrees(parent, subtree_sizes, x, y)

    # Print the resulting MST
    for node1, node2, weight in result:
        print("%d - %d: %d" % (node1, node2, weight))

このアルゴリズム自体は、前に説明したすべてのメソッドを組み合わせたものである。まず最初に、辺のリストを重みでソートし、 parent と subtree_sizes 配列を初期化します。そして，ソートされた辺のリストを繰り返し，それらを 1 つずつ選択し，可能であれば結果の木に追加していきます．アルゴリズムは、生成された木の辺の数が (num_of_nodes - 1) と等しくなった時点で停止する。結果として得られる木は、これまで構築しようとしてきた最小木である。

このアルゴリズムを、前に使ったグラフの例でテストしてみよう。

例題のグラフでクラスカルのアルゴリズムをテストする

まず最初に、例のグラフを表現する Graph オブジェクトを作成する必要があります。

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

次に、add_edge() メソッドを使用して、サンプルグラフのすべてのノードを example_graph に追加します。

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.kruskals_mst()

すると、以下のような出力が得られます。

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

見てわかるように、この出力は、「クラスカルのアルゴリズム説明」のセクションで説明したものと同じMSTを記述しています。出力の各行は、次のように1つのエッジを表している。ノード1 – ノード2：重み`。構築されたMSTを以下の図に示す。

クラスカルのアルゴリズムの複雑さとは？

E個のエッジとN個のノードを持つグラフがあるとする。クラスカルのアルゴリズムを用いてMSTを求めるのにかかる時間はO(E log E)であり、これはO(E log N)` と等しい。

結論

クラスカルのアルゴリズムは、プリムのアルゴリズムやボルエフカのアルゴリズムと並んで、グラフの最小スパニングツリーを求めるためのアルゴリズムとして最もよく使われているものである。それぞれの複雑さはほぼ同じなので、どれを使うかはあなた次第です。

この記事では、実用的な例でクラスカのアルゴリズムを説明し、実際の実装をあげましたので、あなたのプロジェクトで使用し、どのように動作するかを理解することができます。