最小全域木問題 NetworkX

最小全域木問題

最小全域木問題 (Minimum Spanning Tree Problem) とは、グラフ理論において、与えられた重みつき無向グラフに対して、そのグラフの全ての頂点を含む木（連結かつ閉路を持たないグラフ）のうち、辺の重みの和が最小になるような木を求める問題です。

問題

以下の図のグラフにおいて、全ての頂点を繋ぐ最小コストの辺集合を求めてください。

     2     3
 A ----- B ----- C
 |   4 / |   5 / |
 |   /   |   /   |
 1 /     4 /     | 1
 | /     | /     |
 |/      |/      |
 D ----- E ----- F
     5     4

解法・ソースコード

最初に、networkxライブラリをnxという名前でインポートします。

次に、空のグラフを作成し、add_weighted_edges_from()メソッドで、頂点間の辺を加えます。

ここで、(‘A’, ‘B’, 2)というように、3つ目の引数で辺の重みを指定しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import networkx as nx

# グラフを作成
G = nx.Graph()
G.add_weighted_edges_from([
    ('A', 'B', 2),
    ('A', 'D', 1),
    ('B', 'C', 3),
    ('B', 'E', 4),
    ('B', 'D', 4),
    ('C', 'E', 5),
    ('C', 'F', 1),
    ('D', 'E', 5),
    ('E', 'F', 4)
])

次に、minimum_spanning_tree()メソッドを使って、最小全域木を求めます。

このメソッドは、引数にグラフを取り、最小全域木を構成する辺集合を返します。

最後に、print()関数を使って、最小全域木を構成する辺集合を表示しています。

edges()メソッドを使うことで、辺集合を取得できます。

1
2
3
4
5
# 最小全域木を求める
mst = nx.minimum_spanning_tree(G)

# 結果を表示
print(mst.edges())

実行すると、以下のように最小全域木を構成する辺集合が表示されます。

[実行結果]
[('A', 'D'), ('A', 'B'), ('B', 'C'), ('B', 'E'), ('E', 'F')]