講義「アルゴリズムとデータ構造」

講義「アルゴリズムとデータ構造」

第１３回 グラフとネットワークのアルゴリズム(2)

大学院情報科学研究院 情報理工学部門 情報知識ネットワーク研究室

喜田拓也

2019/5/21 講義資料

今日の内容

グラフとは （おさらい）

グラフ 𝐺𝐺 に対する全域木について 全域木（スパニング木）

最小全域木（最小スパニング木）

最小全域木を求めるアルゴリズムについて クラスカルのアルゴリズム

クラスカルのアルゴリズムの高速化

クラスカルのアルゴリズムが正しいことの証明

時間計算量が O 𝑚𝑚 log 𝑛𝑛 であることの証明

無向グラフ 有向グラフ

グラフとは （おさらい）

頂点 (vertex) の集合 𝑉𝑉 と辺 (edge) の集合 𝐸𝐸 ⊆ 𝑉𝑉 × 𝑉𝑉 の組 (𝑉𝑉, 𝐸𝐸) 𝑣𝑣 ₀

𝑣𝑣 ₁

𝑣𝑣 ₂ 𝑣𝑣 ₃

𝑣𝑣 ₄ 𝑒𝑒 ₀

𝑒𝑒 ₁ 𝑒𝑒 ₂ 𝑒𝑒 ₃

𝑒𝑒 ₄

𝑒𝑒 ₅ 𝑣𝑣 ₀

𝑣𝑣 ₁

𝑣𝑣 ₂ 𝑣𝑣 ₃

𝑣𝑣 ₄ 𝑒𝑒 ₀

𝑒𝑒 ₁ 𝑒𝑒 ₂ 𝑒𝑒 ₃

𝑒𝑒 ₄ 𝑒𝑒 ₅

𝑣𝑣 ₀ 𝑣𝑣 ₁

𝑣𝑣 ₂ 𝑣𝑣 ₃

𝑣𝑣 ₄ 2

3 4

2

1

2 𝑣𝑣 ₀

𝑣𝑣 ₁

𝑣𝑣 ₂ 𝑣𝑣 ₃

𝑣𝑣 ₄ 2

3 4

2

1

2

無向ネットワーク 有向ネットワーク

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

※ 無向グラフの場合は，各辺を両方向の２辺からなる有向グラフとみなして表現する

グラフの表現のしかた （おさらい）

𝑣𝑣 ₀ 𝑣𝑣 ₁

𝑣𝑣 ₂ 𝑣𝑣 ₃

𝑣𝑣 ₄ 𝑒𝑒 ₀

𝑒𝑒 ₁ 𝑒𝑒 ₂ 𝑒𝑒 ₃

𝑒𝑒 ₄ 𝑒𝑒 ₅

𝑣𝑣 ₀ 𝑣𝑣 ₁

𝑣𝑣 ₂ 𝑣𝑣 ₃

𝑣𝑣 ₄ 2

3 4

2

1 2

0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

0 2 4 0 0 0 0 3 0 0 0 0 0 2 0 0 0 0 0 1 2 0 0 0 0

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

𝑣𝑣

隣接行列

0 1 2 3 4

2

1

2

3

4

0

0 1 2 3 4

2 3

3 2

4 1

0 2

1 2 2 4

隣接リスト

グラフ 𝐺𝐺 に対する全域木 (spanning tree)

深さ優先の全域木 幅優先の全域木

定義：

「グラフ 𝐺𝐺𝐺 はグラフ 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) の全域木（スパニング木）である」

⇕

「 𝐺𝐺𝐺 は 𝐺𝐺 のすべての頂点を含む部分グラフで木になっているもの」

【路 (path) 】 辺でつながった頂点の列

【閉路 (cycle) 】 自分に戻ってくるような路（長さは 3 頂点以上）

グラフ 𝐺𝐺 が連結 ⇔ 𝐺𝐺 の任意の頂点対が路でつながっている グラフ 𝐺𝐺 が木 ⇔ 𝐺𝐺 は閉路のない連結グラフ

𝑣𝑣 ₀ 𝑣𝑣 ₁

𝑣𝑣 ₂

𝑣𝑣 ₃ 𝑣𝑣 ₄ 𝑣𝑣 ₅ 𝑣𝑣 ₆

𝑣𝑣 ₇

𝑣𝑣 ₀ 𝑣𝑣 ₁

𝑣𝑣 ₂

𝑣𝑣 ₃ 𝑣𝑣 ₄ 𝑣𝑣 ₅ 𝑣𝑣 ₆

𝑣𝑣 ₇

ネットワーク 𝐺𝐺 の最小全域木 (minimum spanning tree)

定義：

グラフ 𝐺𝐺𝐺 はネットワーク（重み付きグラフ） 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) の 最小全域木（最小スパニング木）である

𝐺𝐺𝐺 は 𝐺𝐺 の全域木で含まれる辺の重みの総和が最小のもの ⇕

𝐺𝐺 の最小スパニング木

3 4

2 5 1

2 7

ネットワーク 𝐺𝐺

4 2 1

2

応用例として，通信網の設計，ガス・水道の配管設計などがある

最小全域木を求めるアルゴリズム

• プリム (Prim) のアルゴリズム

1930 年に Vojtěch Jarník （ヤルニーク）が開発．

それとは独立に 1957 年に Prim により開発された．

また， 1959 年には Dijkstra により再発見された．

DJP 法， Jarník 法， Jarník-Prim 法とも呼ばれる．

最小全域木が構成されている連結成分の範囲 を徐々に広げていくという方針で求める．

Joseph B. Kruskal 1928-2010 , USA

Robert Clay Prim (1921-?), USA

最小全域木 (MST) を求める代表的なアルゴリズム

• クラスカル (Kruskal) のアルゴリズム

1956 年に Joseph Kruskal （ジョセフ・クラスカル）に よって提案された．重みが小さい辺から選択し，

現在の解に追加していくという方針で求める．

[考え方] 解候補 𝑇𝑇 を空集合から始めて，重みが小さい辺から選 択し，現在の解候補 𝑇𝑇 に加えていく．ただし，選択することにより閉 路ができる場合は選択しない．

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

クラスカルのアルゴリズムの解候補 𝑇𝑇 がもつ性質

• 𝑇𝑇 は閉路を含まない

• 𝑇𝑇 は，森になっている（必ずしも連結しているとは限らない）

※ グラフ 𝐺𝐺 が森 ⇔ 𝐺𝐺 は閉路のないグラフ

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7 _{閉路ができる！}

クラスカルのアルゴリズム（疑似コード）

Procedure MST-Kruskal( 𝐺𝐺 : グラフ , 𝑤𝑤 : 重み ) 1: 𝑇𝑇 ← φ; // 解 𝑇𝑇 は最初は空

2: 辺の配列 𝑒𝑒 を重みの小さい順 𝑒𝑒 0 , … , 𝑒𝑒[𝑚𝑚 − 1] に整列する ; 3: for 𝑖𝑖 ← 0, 1, … , 𝑚𝑚 − 1 do

4: if ( 𝑇𝑇 ∪ 𝑒𝑒 𝑖𝑖 が閉路を含まない ) then

5: 𝑇𝑇 ← 𝑇𝑇 ∪ 𝑒𝑒 𝑖𝑖 ;

6: end if 7: end for

6: 最小全域木 𝑇𝑇 を出力する ;

このチェックは 意外に難しい！

単純にやると毎回 O(𝑛𝑛) 時間 かかる（全体では O(𝑚𝑚𝑛𝑛) ）

（ヒント： 𝑒𝑒[𝑖𝑖] の一方の頂点

から 𝑇𝑇 を探索をする）

練習問題： 最小全域木を求めてみよう！

3 1

2 3

2 1

問 1 問 2

問 3 問 4

2 1 3

2 3

1

3 1

2 1 1 3

4 4

4 2

1

1 3

4 3 3

1 2

1

1 4 4

4 2

1

3 3

1 2

1

1 4 4

4 2

1

解決法

𝑇𝑇 の連結成分毎に，頂点に異なる「色」を 塗っておいて，新しく加えた辺 𝑒𝑒[𝑖𝑖] の両端の 色を比べることでチェックできる！

「色」のグループを表すのには，

Union-Find データ構造を使う

両端が異なる色のときは，辺を 加えても閉路はできない

辺を加えたら色を塗り直す

良い辺

悪い辺

両端が同じ色のときは，辺を 加えると閉路ができる

クラスカルのアルゴリズムの高速化

単純に塗り直すと毎回

O(𝑛𝑛) 時間かかる

Union-Find で

O(log 𝑛𝑛) 時間に

「色」（グループ番号）をもつグループ分けを管理するデータ構造 次の二つの演算を毎回 O(log 𝑛𝑛) 時間で実行できる

• Union( 𝑖𝑖 , 𝑗𝑗 ): 番号 𝑖𝑖 のグループと番号 𝑗𝑗 のグループを合併する

• Find( 𝑖𝑖 ): 番号 𝑖𝑖 のグループ番号を返す

Union-Find データ構造

色の塗り直しに相当 ただし色は選べない

Union(1,2) Union(2,7)

色： 1, 2, 7

1 2 7

5 3 8

4 6

色： 2, 7

1 2 7

5 3 8

4 6

色： 2

1 2 7

5 3 8

4 6

Find(1) → 1 Find(4) → 2 Find(6) → 7

Find(1) → 2 Find(4) → 2 Find(6) → 7

Find(1) → 2 Find(4) → 2 Find(6) → 2

代表元

（色を表す）

12

集合のグループ分けを，木のあつまり（森）で表現する

各グループは，要素番号を頂点ラベルとする一つの木に対応する グループの色は，対応する木の根がもつ要素番号とする

Union-Find データ構造の実現方法

Union(1,2) Union(2,7)

1 5

2

3 4

7

6 8 1

5

2

3 4

7

6 8 1

5

2

3 4 7

6 8

Find( 𝑖𝑖 ): 番号 𝑖𝑖 の頂点から親をたどり，根の番号を返す

Union( 𝑖𝑖 , 𝑗𝑗 ): 番号 𝑖𝑖 と番号 𝑗𝑗 が属する木をマージする．ただし，高さが低い方の木 の根を高い方の木の根の子とする（高さが同じ場合はどちらでもよい）

どちらも O(log 𝑛𝑛) （ 𝑛𝑛 は要素数） ※ Find( 𝑖𝑖 ) の証明はそれほど自明ではない

【補題】 (𝑉𝑉, 𝐸𝐸) を連結無向グラフとし， 𝑆𝑆 ⊆ 𝐸𝐸 とする．このとき，以 下の条件は，部分グラフ (𝑉𝑉, 𝑆𝑆) が (𝑉𝑉, 𝐸𝐸) の最小全域木であるため の必要十分条件である．

条件： 部分グラフ (𝑉𝑉, 𝑆𝑆) は (𝑉𝑉, 𝐸𝐸) の全域木で，すべての 𝑒𝑒 ∈ 𝐸𝐸 − 𝑆𝑆 に対して，

𝑤𝑤 𝑒𝑒 ≥ 𝑤𝑤 𝑒𝑒 ^′ for all 𝑒𝑒𝑒 ∈ 𝐶𝐶 _𝑆𝑆 𝑒𝑒

ただし， 𝑤𝑤(𝑒𝑒) は辺 𝑒𝑒 の重みを表し， 𝐶𝐶 _𝑆𝑆 𝑒𝑒 は辺 𝑒𝑒 と 𝑆𝑆 の辺に よって作られる閉路に含まれる 𝑇𝑇 の辺集合を表す．

クラスカルのアルゴリズムのベースとなる補題

𝐸𝐸 − 𝑆𝑆 は差集合

（ 𝐸𝐸 ∖ 𝑆𝑆 とも書く）

𝑒𝑒

※ 太線： 𝑆𝑆 ， 細線： 𝐸𝐸 − 𝑆𝑆 ， 赤色太線： 𝐶𝐶

𝑒𝑒 3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7

𝑒𝑒

𝑒𝑒

よって， (𝑉𝑉, 𝑆𝑆) が最小全域木であれば必ず条件を満たす．

補題の証明（前半： ⇒ の証明）

𝑒𝑒

𝑒𝑒𝑒 𝐶𝐶 _𝑆𝑆 𝑒𝑒

𝑤𝑤 𝑒𝑒 < 𝑤𝑤 𝑒𝑒 ^′

これを取って

これを付ける

「 𝑉𝑉, 𝑆𝑆 は最小全域木」 ⇒ 「 𝑤𝑤 𝑒𝑒 ≥ 𝑤𝑤 𝑒𝑒 ^′ for all 𝑒𝑒 ^′ ∈ 𝐶𝐶 _𝑆𝑆 𝑒𝑒 」

(𝑉𝑉, 𝑆𝑆) が最小全域木なのに条件を満たさないと仮定する．

すると，仮定より，ある 𝑒𝑒 ∈ 𝐸𝐸 − 𝑆𝑆 が存在し，ある 𝑒𝑒 ^′ ∈ 𝐶𝐶 _𝑆𝑆 𝑒𝑒 に対して 𝑤𝑤 𝑒𝑒 < 𝑤𝑤 𝑒𝑒 ^′ が成り立つ．

𝑉𝑉, 𝑆𝑆 ∪ 𝑒𝑒 − 𝑒𝑒 ^′ は (𝑉𝑉, 𝐸𝐸) の全域木であり，

(𝑉𝑉, 𝑆𝑆) よりも辺の重みの和が小さい．

これは (𝑉𝑉, 𝑆𝑆) が最小全域木であることに矛盾する．

補題の証明（後半： ⇐ の証明）

𝑒𝑒 ∈ 𝑆𝑆 ^∗ − 𝑆𝑆 が存在したとする． 𝑒𝑒 により分かれる二つの連結成分を

𝑉𝑉 ₀ , 𝑆𝑆 ₀ ^∗ , 𝑉𝑉 ₁ , 𝑆𝑆 ₁ ^∗ とすると， 𝑒𝑒 ^′ ∈ 𝐶𝐶 _𝑆𝑆 𝑒𝑒 で二つの連結成分 𝑉𝑉 ₀ , 𝑆𝑆 ₀ ^∗ , 𝑉𝑉 ₁ , 𝑆𝑆 ₁ ^∗ をまたぐ辺 𝑒𝑒 ^′ ∈ 𝑆𝑆 が存在する．

(𝑉𝑉, 𝑆𝑆) は条件を満たしており， 𝑤𝑤 𝑒𝑒 ≥ 𝑤𝑤 𝑒𝑒 ^′ が成り立つので，

𝑆𝑆 ^′ = 𝑆𝑆 ^∗ ∪ 𝑒𝑒 ^′ − 𝑒𝑒 とすれば， 𝑆𝑆 ^′ の重みの総和は 𝑆𝑆 ^∗ の重みの総 和以下になる． 𝑆𝑆 ^∗ は最小全域木なので， 𝑆𝑆 ^′ も 𝑆𝑆 ^∗ と重みの総和が 等しい最小全域木であり， 𝑆𝑆 ^∗ − 𝑆𝑆 > 𝑆𝑆 ^′ − 𝑆𝑆 を満たす．ただし，

|𝑆𝑆| は集合 𝑆𝑆 の要素数を表すものとする．したがって， 𝑆𝑆 ^′ を 𝑆𝑆 ^∗ として 同じ操作を繰り返すと 𝑆𝑆 ^′ = 𝑆𝑆 となり， 𝑆𝑆 も 𝑆𝑆 ^∗ と重みの総和が等しい 最小全域木であることが示される．

【証明終わり】

2 3 2

3

𝑒𝑒 𝑒𝑒 ^′

2 3

3 𝑒𝑒

𝑒𝑒𝑒 𝑆𝑆𝑒

2 3

𝑆𝑆 𝑆𝑆 ^∗

𝑉𝑉

, 𝑆𝑆

𝑉𝑉

, 𝑆𝑆

𝑆𝑆 ^′′

「 𝑉𝑉, 𝑆𝑆 は最小全域木」 ⇐ 「 𝑤𝑤 𝑒𝑒 ≥ 𝑤𝑤 𝑒𝑒 ^′ for all 𝑒𝑒 ^′ ∈ 𝐶𝐶 _𝑆𝑆 𝑒𝑒 」

最小全域木の一つを 𝑉𝑉, 𝑆𝑆 ^∗ とする．条件を満たす 𝑉𝑉, 𝑆𝑆 の

辺の重みの和は 𝑉𝑉, 𝑆𝑆 ^∗ の辺の重みの和に等しいことを示す．

いま， 𝑆𝑆 ₀ に含まれる辺の端点の集合を 𝑉𝑉 ^′ とし， 𝑉𝑉 ^′ = 𝑉𝑉 を示す．

𝑉𝑉 ^′ ≠ 𝑉𝑉 と仮定すると，ある頂点 𝑣𝑣 ∈ 𝑉𝑉 − 𝑉𝑉 ^′ が存在する． (𝑉𝑉, 𝐸𝐸) は 連結であるので，ある頂点 𝑢𝑢 ∈ 𝑉𝑉 ^′ が存在して， 𝑉𝑉 ^′ の頂点を経由 しないで 𝑣𝑣 へ到達する路が存在する．その路に属する辺を 𝑆𝑆 ₀ に 加えても閉路はできない．これはアルゴリズムの「閉路ができな い限り辺を加える」という動作に矛盾する．よって 𝑉𝑉 ^′ = 𝑉𝑉 となり，

(𝑉𝑉, 𝑆𝑆 ₀ ) は全域木であることが示された．

クラスカルのアルゴリズムが正しいことの証明

次に，すべての 𝑒𝑒 ∈ 𝐸𝐸 − 𝑆𝑆 ₀ ，すべての 𝑒𝑒 ^′ ∈ 𝐶𝐶 _𝑆𝑆

𝑒𝑒 に対して 𝑤𝑤 𝑒𝑒 ≥ 𝑤𝑤 𝑒𝑒 ^′ が成り 立つことを示す．ある 𝑒𝑒 ∈ 𝐸𝐸 − 𝑆𝑆 ₀ が存在して，ある 𝑒𝑒 ^′ ∈ 𝐶𝐶 _𝑆𝑆

𝑒𝑒 に対して 𝑤𝑤 𝑒𝑒 <

𝑤𝑤 𝑒𝑒 ^′ が成り立ったと仮定する．すると， MST-Kruskal アルゴリズムの４行目において

𝑆𝑆 ∪ 𝑒𝑒 が閉路を持つか否かチェックするときには，

𝑒𝑒

𝑒𝑒𝑒 𝐶𝐶 _𝑆𝑆

𝑒𝑒

𝑤𝑤 𝑒𝑒 < 𝑤𝑤 𝑒𝑒 ^′

（証明） クラスカルのアルゴリズムにより求めた辺の集合を 𝑆𝑆 ₀ とする．このとき，補 題の条件が成り立っていることを示せばよい．

まず， (𝑉𝑉, 𝑆𝑆 ₀ ) が全域木であることを示す． (𝑉𝑉, 𝑆𝑆 ₀ ) は明らかに閉路を持たない．

𝑉𝑉 ^′ 𝑣𝑣

𝑢𝑢

𝑉𝑉

𝑆𝑆 にはまだ 𝑒𝑒 ^′ は含まれていないので， 𝑆𝑆 ∪ 𝑒𝑒 は閉路を持た ないことになり 𝑆𝑆 ₀ が 𝑒𝑒 を含んでいないことに矛盾する．

よって，補題の条件が成り立つ．したがって， (𝑉𝑉, 𝑆𝑆 ₀ ) は 最小全域木である． 【証明終わり】

こっち

が先

（証明） 頂点数 𝑛𝑛 ，辺数 𝑚𝑚 のグラフ 𝐺𝐺 に対して，アルゴリズム MST- Kruskal にかかる時間を考える．

1 行目は明らかに O(1) 時間でできる．

2 行目の辺のソートは， 𝑚𝑚 個のソートなので O(𝑚𝑚 log 𝑚𝑚) であるが，

𝑚𝑚 ≤ 𝑛𝑛 ² なので O(𝑚𝑚 log 𝑛𝑛) ．

3 〜 7 行目の for ループでは，各繰り返しにつき，高々 𝑛𝑛 − 1 回の Union と，高々 2𝑚𝑚 回の Find を実行する． Union と Find は O(log 𝑛𝑛) 時 間でできるから， O 𝑛𝑛 + 𝑚𝑚 × O log 𝑛𝑛 = O 𝑛𝑛 + 𝑚𝑚 log 𝑛𝑛 時間．

連結グラフで考えているので 𝑛𝑛 − 1 ≤ 𝑚𝑚 である．すなわち， for ルー プ全体は O(𝑚𝑚 log 𝑛𝑛) 時間で実行できる．

したがって，全体の計算時間は O 𝑚𝑚 log 𝑛𝑛 で実行できる．

【証明終わり】

クラスカルのアルゴリズムの最悪時間計算量は O(𝑚𝑚 log 𝑛𝑛)

練習問題： 最小全域木を求めてみよう！

3 1

2 3

2 1

問 1 問 2

問 3 問 4

2 1 3

2 3

1

3 1

2 1 1 3

4 4

4 2

1

1 3

4 3 3

1 2

1

1 4 4

4 2

1

3 3

1 2

1

1 4 4

4 2

1