最小全域木問題

問題

頂点数 $N$、辺数 $M$ のグラフがあります。

頂点には $1$ から $N$ までの番号が付けられており、辺 $i$ は頂点 $A_i$ と $B_i$ を双方向に結ぶ長さ $C_i$ の辺です。

このグラフの最小全域木における辺の長さの総和を求めて下さい。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ 1 \leqq M \leqq 100000 $
🔹$ 1 \leqq C_i \leqq 10000 $
🔹このグラフは連結である。

解き方

全域木とは、$M$ 個の辺の中からいくつかを選んで作った全ての頂点が繋がっている木のことです。

全域木の中でも「長さの合計」が最小となるものを最小全域木といいます。

最小全域木は『短い辺から追加していく』という単純な貪欲法によって導き出すことができます。

この方法はクラスカル法と呼ばれており、配列のソートとUnion-Find木を使って実装することができます。

ソースコード解説

下記のソースコードは、Union-Find 木を使って与えられたグラフの連結成分を管理し、クエリーを処理するプログラムです。

入力例１では、3つの頂点と4つのクエリーが与えられています。

クエリー１は頂点同士を結ぶ辺を追加し、クエリー２は２つの頂点が同じ連結成分に属するかを判定するものです。

まず、Union-Find 木のクラスを定義しています。

コンストラクタでは、頂点数 n を受け取り、par と size の初期化を行っています。

par は親の頂点を保持する配列で、初期値は全て -1 です。

size はグループの頂点数を保持する配列で、初期値は全て 1 です。

次に、root 関数では、引数で指定された頂点 x の根を探索して返します。

par[x] が -1 になるまで、頂点 x の親に移動していきます。

unite 関数は、引数で指定された要素 u, v を同一のグループに統合します。

この関数内では、それぞれの根を取得し、もし根が異なる場合はグループの頂点数が小さい方を大きい方に統合します。

par 配列には親の頂点を、size 配列にはグループの頂点数を記録しています。

same 関数は、引数で指定された要素 u, v が同一のグループに属するかどうかを判定します。

この関数内では、root 関数を呼び出して u, v の根を比較します。

次にクエリーの処理を行います。

クエリー１の場合は、union 関数を呼び出して頂点 u, v を統合します。

クエリー２の場合は、same 関数を呼び出して頂点 u, v が同一のグループに属するかどうかを判定します。

最後に最小全域木における辺の長さの総和を出力しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#-------- 入力例１ ---------
N = 7       # 頂点数
M = 9       # 辺数
# つながっている２つの頂点とその長さ
edges = [
    (1, 2, 12),
    (1, 3, 10),
    (2, 6, 160),
    (2, 7, 15),
    (3, 4, 1),
    (3, 5, 4),
    (4, 5, 3),
    (4, 6, 120),
    (6, 7, 14)
]
#---------------------------
# Union-Find 木
class unionfind:
    # n 頂点の Union-Find 木を作成
    def __init__(self, n):
        self.n = n
        self.par = [ -1 ] * (n + 1) # 最初は親が無い
        self.size = [ 1 ] * (n + 1) # 最初はグループの頂点数が 1
    
    # 頂点 x の根を返す関数
    def root(self, x):
        # 1 個先（親）がなくなるまで進み続ける
        while self.par[x] != -1:
            x = self.par[x]
        return x
    
    # 要素 u, v を統合する関数
    def unite(self, u, v):
        rootu = self.root(u)
        rootv = self.root(v)
        if rootu != rootv:
            # u と v が異なるグループのときのみ処理を行う
            if self.size[rootu] < self.size[rootv]:
                self.par[rootu] = rootv
                self.size[rootv] += self.size[rootu]
            else:
                self.par[rootv] = rootu
                self.size[rootu] += self.size[rootv]
    
    #  要素 u と v が同一のグループかどうかを返す関数
    def same(self, u, v):
        return self.root(u) == self.root(v)

# 辺を長さの小さい順にソート
edges.sort(key = lambda x: x[2])

# 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
    if not uf.same(a, b):
        uf.unite(a, b)
        answer += c

# 答えの出力
print('解：', answer)

[実行結果（入力例１）]

解： 55

最小全域木における辺の長さの総和を求めることができました。