ボルエブカのアルゴリズムは、グラフ理論で知られるチェコの数学者、オタカル・ボルエブカが発表した貪欲アルゴリズムである。
その最も有名な応用例として、グラフの最小木（minimum spanning tree）を求めることができる。
このアルゴリズムで特筆すべきことは、記録上最も古い最小木アルゴリズムであるということです。
Borůvkaは1926年にこれを考え出したが、それは我々が今日知っているようなコンピュータがまだ存在する前であった。
効率的な電力網を構築するための方法として発表された。
この授業では、グラフとは何か、最小分散木とは何かについて復習した後、Borůvkaのアルゴリズムに飛びつき、Pythonで実装します。
グラフと最小スパニングツリー
グラフとは、ノード（頂点）と呼ばれる特定のオブジェクトのグループを表し、それらのノードの特定のペアが接続または関連している抽象的な構造である。
これらの接続はそれぞれエッジと呼ばれる。
木はグラフの一例である。
上の画像では、最初のグラフは4つのノードと4つのエッジを持ち、2番目のグラフ（2分木）は7つのノードと6つのエッジを持っています。
グラフは、地理空間位置からソーシャルネットワークグラフやニューラルネットワークまで、多くの問題に適用できる。
概念的には、このようなグラフは私たちの身の回りに溢れている。
例えば、家系図を作ったり、大切な人との出会いを誰かに説明したりするとしよう。
このとき、私たちが感じたのと同じように、聞く人にとっても興味深い話にするために、たくさんの人とその関係を紹介するかもしれません。
これはまさに、人（ノード）とその関係（エッジ）のグラフなので、グラフはこれを視覚化する素晴らしい方法なのです。
グラフの種類
グラフが持つ辺の種類によって、2種類のグラフに分類される。
- 無向グラフ
- 有向グラフ
無向グラフは、辺に向きがないグラフである。
無向グラフは、辺に向きがないグラフであり、すべての辺は双方向とみなされる。
形式的には，無向グラフは G = (V, E) と定義できる．ここで， V はグラフのすべてのノードの集合であり， E は E の要素の無秩序なペアを含む集合で，エッジを表している．
ここでいう順序なしのペアとは、2つのノード間の関係が常に両側であることを意味します。
つまり、 A から B へ向かう辺があるとわかっていれば、 B から A へ向かう辺も確実にあることがわかります。
有向グラフとは、辺に向きがあるグラフのことである。
ここで、Vはグラフのすべてのノードの集合であり、EはEからの要素の順序付きペアを含む集合である。
順序付きペアは、2つのノード間の関係が片面または両面のいずれかになることを意味する。
つまり、AからBに向かう辺があったとしても、BからAに向かう辺があるかどうかはわからないということである。
エッジの方向は矢印で示される。
2辺の関係は、2つの異なる矢印を描くか、同じエッジの両側に2つの矢印のポイントを描くことで示すことができることに注意してください。
グラフをエッジで区別するもう一つの方法は、エッジの重さに関するものである。
それに基づいて、グラフは以下のようになる。
- 重み付き
- 重み付けなし
重み付きグラフは、すべての辺に重みとなる数値が割り当てられているグラフである。
この重みは、解く問題によって、ノード間の距離、容量、価格などを表すことができます。
ということです。
重み付きグラフは、最短距離を求める問題や、これから説明するように最小木構造を求める問題など、かなり頻繁に利用されています。
gt; 重みのないグラフは、辺に重みを持ちません。
注：この記事では、無向きの重み付きグラフに焦点を当てます。
グラフには、連結と切断がある。
グラフは、各対のノード間にパス（1つ以上のエッジで構成される）がある場合、連結していると言える。
一方、グラフが切断されているのは、エッジのパスで結ばれていないノードのペアがある場合である。
木と最小スパニングツリー
木、部分グラフ、スパニングツリーについては、かなり多くのことが語られているが、ここでは、本当に素早く、簡潔に説明する。
- 木は無向グラフで、2つのノードがちょうど1つのパスで結ばれており、それ以上でも以下でもない。
- グラフ
Aの部分グラフとは、グラフAのノードとエッジの部分集合で構成されたグラフのことです。 - グラフ
Aの部分グラフとは、グラフAのノードとエッジの部分集合で構成されるグラフのことである。 - 最小分散木とは，すべての辺の重みの和が最小になるような分散木である．これは木なので（そして辺の重みの和が最小になるはずなので）、サイクルは存在しないはずです。
注：グラフの辺の重みがすべて異なる場合、そのグラフの最小木は一意になる。
しかし、辺の重みが明確でない場合は、1つのグラフに対して複数の最小生成木が存在する可能性があります。
さて、グラフの理論がわかったところで、アルゴリズムそのものに取り組みます。
実装
これから扱う主なデータ構造である Graph クラスを実装します。
まず、コンストラクタから始めましょう。
class Graph:
def __init__(self, num_of_nodes):
self.m_v = num_of_nodes
self.m_edges = []
self.m_component = {}
このコンストラクタでは、グラフのノード数を引数として与え、3つのフィールドを初期化する。
-
m_v– グラフのノードの数。 -
m_edges– エッジのリスト． -
m_component– ノードが所属するコンポーネントのインデックスを格納する辞書。
では、グラフのノードにエッジを追加するために利用するヘルパー関数を作ってみましょう。
def add_edge(self, u, v, weight):
self.m_edges.append([u, v, weight])
この関数は [first, second, edge weight] というフォーマットでグラフにエッジを追加する。
最終的には2つのコンポーネントを統合するメソッドを作りたいので、まず、与えられたコンポーネント全体に新しいコンポーネントを伝播させるメソッドが必要になります。
そして次に、与えられたノードのコンポーネントインデックスを見つけるメソッドが必要です。
def find_component(self, u):
if self.m_component[u] == u:
return u
return self.find_component(self.m_component[u])
def set_component(self, u):
if self.m_component[u] == u:
return
else:
for k in self.m_component.keys():
self.m_component[k] = self.find_component(k)
このメソッドでは、辞書を人工的にツリーとして扱います。
このメソッドでは、辞書を人工的にツリーとして扱います。
コンポーネントのルートを見つけたかどうかを尋ねます(ルートコンポーネントだけが常に m_component 辞書で自分自身を指すからです)。
ルートノードが見つからなかった場合は、現在のノードの親ノードを再帰的に検索します。
注意: m_components が正しいコンポーネントを指していると仮定しない理由は、コンポーネントの統一を開始するときに、確実にコンポーネントインデックスを変更しないとわかっているのは、ルートコンポーネントだけだからです。
例えば、上の例のグラフでは、最初の繰り返しで、辞書は次のようになります。
| インデックス｜値｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜｜）。
9`のコンポーネントがあり、各メンバーがそれ自体でコンポーネントになっています。
2回目の繰り返しでは、このようになります。
| インデックス | 値 |
|---|---|
| 0 | 0 |
| 2 | 2 |
| 3 | 3 |
| 4 | 2 |
| 5 | 3 |
| 6 | 7 |
| 7 | 4 |
さて、根っこをたどると、新しい構成要素は次のようになることがわかります。
0, 1},そして` です。
アルゴリズム自体を実装する前に必要な最後のメソッドは、それぞれのコンポーネントに属する2つのノードが与えられたときに、2つのコンポーネントを1つに統合するメソッドです。
def union(self, component_size, u, v):
if component_size[u] <= component_size[v]:
self.m_component[u] = v
component_size[v] += component_size[u]
self.set_component(u)
elif component_size[u] >= component_size[v]:
self.m_component[v] = self.find_component(u)
component_size[u] += component_size[v]
self.set_component(v)
print(self.m_component)
この関数では、2つのノードの成分の根（これは同時に成分のインデックスでもある）を見つける。
次に、構成要素の大きさを比較し、小さい方を大きい方にくっつける。
そして、小さい方のサイズを大きい方のサイズに足すだけで、1つの成分になってしまうからである。
最後に、同じサイズのコンポーネントがあれば、それらを好きなように結合します。
この例では、2番目のコンポーネントを1番目のコンポーネントに追加することで結合しています。
これで必要なユーティリティメソッドをすべて実装したので、いよいよBorůvkaのアルゴリズムに飛び込むことができる。
def boruvka(self):
component_size = []
mst_weight = 0
minimum_weight_edge = [-1] * self.m_v
for node in range(self.m_v):
self.m_component.update({node: node})
component_size.append(1)
num_of_components = self.m_v
print("---------Forming MST------------")
while num_of_components > 1:
for i in range(len(self.m_edges)):
u = self.m_edges[i][0]
v = self.m_edges[i][1]
w = self.m_edges[i][2]
u_component = self.m_component[u]
v_component = self.m_component[v]
if u_component != v_component:
if minimum_weight_edge[u_component] == -1 or
minimum_weight_edge[u_component][2] > w:
minimum_weight_edge[u_component] = [u, v, w]
if minimum_weight_edge[v_component] == -1 or
minimum_weight_edge[v_component][2] > w:
minimum_weight_edge[v_component] = [u, v, w]
for node in range(self.m_v):
if minimum_weight_edge[node] != -1:
u = minimum_weight_edge[node][0]
v = minimum_weight_edge[node][1]
w = minimum_weight_edge[node][2]
u_component = self.m_component[u]
v_component = self.m_component[v]
if u_component != v_component:
mst_weight += w
self.union(component_size, u_component, v_component)
print("Added edge [" + str(u) + " - "
+ str(v) + "]
"
+ "Added weight: " + str(w) + "
")
num_of_components -= 1
minimum_weight_edge = [-1] * self.m_v
print("----------------------------------")
print("The total weight of the minimal spanning tree is: " + str(mst_weight))
このアルゴリズムで最初に行ったことは、アルゴリズムで必要となる追加のリストを初期化することでした。
- コンポーネントのリスト（すべてのノードに初期化される）。
- コンポーネントのリスト（すべてのノードで初期化） * サイズを保持するリスト（
1で初期化）、および最小重量エッジのリスト（最小重量エッジがまだわからないので最初は-1） * コンポーネントのリスト（すべてのノードで初期化）、および最小重量エッジのリスト。
次に、グラフ内のすべてのエッジを調べ、それらのエッジの両側にある成分の根を見つけます。
その後、いくつかの if 節を使用して、これら 2 つのコンポーネントを接続する最小重みのエッジを探します。
- コンポーネント u の現在の最小重量辺が存在しない (
-1である) 場合、または今観測している辺よりも大きい場合、今観測している辺の値を代入することになります。 - コンポーネント v の現在の最小重量エッジが存在しない (
-1である) 場合、または今観測しているエッジよりも大きい場合、現在観測しているエッジの値をそれに代入することになります。
各成分について最も安価なエッジを見つけたら、それらを最小木に追加し、それに応じて成分の数を減らす。
最後に、最小重量エッジのリストをリセットして -1 に戻し、この作業をすべてやり直せるようにします。
構成要素のリストに複数の構成要素がある限り、繰り返し行います。
上の例で使ったグラフを、実装したアルゴリズムの入力として置いてみよう。
g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 6, 7)
g.add_edge(1, 6, 11)
g.add_edge(1, 7, 20)
g.add_edge(1, 2, 9)
g.add_edge(2, 3, 6)
g.add_edge(2, 4, 2)
g.add_edge(3, 4, 10)
g.add_edge(3, 5, 5)
g.add_edge(4, 5, 15)
g.add_edge(4, 7, 1)
g.add_edge(4, 8, 5)
g.add_edge(5, 8, 12)
g.add_edge(6, 7, 1)
g.add_edge(7, 8, 3)
アルゴリズムの実装でチャックすると、次のようになる。
---------Forming MST------------
{0: 1, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge [0 - 1]
Added weight: 4
{0: 1, 1: 1, 2: 4, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge [2 - 4]
Added weight: 2
{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge [3 - 5]
Added weight: 5
{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 6, 7: 4, 8: 8}
Added edge [4 - 7]
Added weight: 1
{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 8}
Added edge [6 - 7]
Added weight: 1
{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 4}
Added edge [7 - 8]
Added weight: 3
{0: 4, 1: 4, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 4}
Added edge [0 - 6]
Added weight: 7
{0: 4, 1: 4, 2: 4, 3: 4, 4: 4, 5: 4, 6: 4, 7: 4, 8: 4}
Added edge [2 - 3]
Added weight: 6
----------------------------------
The total weight of the minimal spanning tree is: 29
このアルゴリズムの時間計算量は O(ElogV) であり、ここで E はエッジの数、V はノードの数を表す。
このアルゴリズムの空間的な複雑さは O(V + E) である．なぜなら，ノード数と同じサイズのリストをいくつか保持し，グラフのすべての辺をデータ構造自身の中に保持しなければならないからである．
結論
Borůvkaのアルゴリズムは、PrimのアルゴリズムやKruskalのアルゴリズムのような他の最小木アルゴリズムほど知られていないにもかかわらず、ほとんど同じ結果を与えます – これらはすべて最小木を見つけ、時間の複雑さはほぼ同じです。
Borůvkaのアルゴリズムが他のアルゴリズムと比較して優れている点は、最小木を見つけるために、エッジをプレソートしたり、優先キューを維持する必要がないことである。
このことは複雑さの助けにはならないが、それでもエッジを logE 回通過させるので、コーディングはもう少し単純になる。