アルゴリズムとデータ構造

アルゴリズムとデータ構造

第10週 グラフ構造と最短路問題

2014年12月4日 金岡 晃

授業計画

1

第1週 (9/25)

データ構造とアルゴリズムの基 礎

第2週 (10/2)

アルゴリズムの効率、線型構造、

スタックと待ち行列 第3週

(10/9)

＜演習＞アルゴリズムの効率、

線型構造、スタックと待ち行列 第4週

(10/16)

文字列照合（KMP法、BM法）

＋＜演習＞

第5週 (10/23)

休講 第6週

(10/30)

木の構造、木の走査、二分木、

決定木 第7週

(11/13)

＜演習＞木の構造、木の走査、

二分木、決定木 第8週

(11/20)

中間試験

第9週 (11/27)

休講 第10週

(12/4)

グラフ構造と最短路問題＋

＜演習＞

第11週 (12/11)

休講 第12週

(12/18)

データ整列：ヒープソート 法、クイックソート法＋＜

演習＞

第13週 (1/8)

データ探索：ハッシュ法、

木構造探索法 →休講 第14週

(1/15)

データ探索：ハッシュ法、

木構造探索法＋＜演習＞

1/21-2/6 期末試験

2014/12/4 アルゴリズムとデータ構造

中間試験：解答と解説

アルゴリズムとデータ構造

2 ^2014/12/4 アルゴリズムとデータ構造

2014/12/4 アルゴリズムとデータ構造

3

問 1-1 ： 𝑂(𝑥) または 𝑂 𝑎

+ 𝑏

問 1-2 ： 省略

問 1-3 ： 省略

＜問 1＞

𝑎² + 𝑏² = 𝑐²を満たす自然数の組(𝑎, 𝑏, 𝑐)をピタゴラス数という。下記のアルゴリズムは与えらえた 2 つの自然 数(𝑎, 𝑏)に対し、𝑎²+ 𝑏² = 𝑐²を満たす𝑐を探すアルゴリズムである。

【アルゴリズム A】

1) 𝑥 = 𝑎²+ 𝑏²を計算する

2) 𝑖 = 1, … , 𝑥に対し、以下を行う

(ア) 𝑖²が𝑥と等しいか確認する。等しい場合、𝑖を出力してアルゴリズムを終了する 3) 見つからなかった旨のメッセージを出力し、アルゴリズムを終了する

アルゴリズム Aに対し、以下を答えよ。

＜問1-1＞ アルゴリズムAの計算量をオーダ記法で示せ

＜問 1-2＞ アルゴリズム A より効率の良いアルゴリズムを示せ。その際、どの点がアルゴリズム A と比較し て効率が良いかを書くこと。その際、利用できる算術演算は「加算」「減算」「乗算」、利用できる比較演算は

「大小比較」「一致比較」のみとする。

＜問1-3＞ 問 1-2 で示したアルゴリズムの計算量をオーダ記法で示せ

2014/12/4 アルゴリズムとデータ構造

4

＜問 2＞

𝑛の階乗𝑛!を求める関数を𝑓(𝑛)とした場合、𝑎² + 𝑏² = 𝑐²𝑛 = 1のときは𝑓(𝑛) = 1で与えられる。𝑛 ≥ 2のときの 𝑓(𝑛)を再帰的手続きを利用して表せ

問 2 ： 𝑓 𝑛 = 𝑛 × 𝑓 𝑛 − 1

2014/12/4 アルゴリズムとデータ構造

5

＜問 3＞

文字列照合のアルゴリズム KMP 法において、文字（アルファベット）が{A, B, C, D} である場合、パターン

ABCABCAB に対するfailを導出せよ。ただし、解答には求めた failだけではなく、導出過程も記載すること。

問 3 ： fail = {0,1,1,0,1,1,0,1}

2014/12/4 アルゴリズムとデータ構造

6

ポイント ポイント

• アルゴリズム（手続き）を意識して書くと良い

• パターンすべてが網羅されているか確認すると良い

＜問 4＞

9 枚のコインがあり、そのうち 1 枚だけが偽物である。偽物は外見は違わないが、重さが異なっているので区別 できる。ただし、偽物が本物より重いのか軽いのか不明である。ここで、天秤を 3 回だけ用いて、どのコインが偽 物でかつそれは本物より重いのか軽いのかを知るにはどうすれば良いか、答えよ。

2014/12/4 アルゴリズムとデータ構造

7

𝑎 + 𝑏 + 𝑐: 𝑑 + 𝑒 + 𝑓 𝑎 + 𝑏 + 𝑐: 𝑑 + 𝑒 + 𝑓

𝑎 + 𝑑: 𝑏 + 𝑒 𝑎 + 𝑑: 𝑏 + 𝑒

𝑎 ∶ 𝑥

𝑎 ∶ 𝑥 𝑐 ∶ 𝑥𝑐 ∶ 𝑥 𝑏 ∶ 𝑥𝑏 ∶ 𝑥

𝑔: ℎ 𝑔: ℎ

𝑔 ∶ 𝑥

𝑔 ∶ 𝑥 ℎ ∶ 𝑥ℎ ∶ 𝑥

> = <

>

=

< > <

𝑎 + 𝑑: 𝑏 + 𝑒 𝑎 + 𝑑: 𝑏 + 𝑒

𝑑 ∶ 𝑥

𝑑 ∶ 𝑥 𝑓 ∶ 𝑥𝑓 ∶ 𝑥 𝑒 ∶ 𝑥𝑒 ∶ 𝑥

>

= <

𝛼: 𝛽

𝛼: 𝛽 _{を左に𝛼、右に𝛽}を載せて天秤で量る動作を表すものとする。

𝛼 + 𝛽: 𝛾 𝛼 + 𝛽: 𝛾

𝑖 ∶ 𝑥 𝑖 ∶ 𝑥

=

での𝛼 + 𝛽は、右に𝛼と𝛽を載せていることを表すものとする。

天秤で量った結果をそれぞれ“>”, “=”, “<”で表し、「左が重い」「釣り合う」「右が重い」

を示すものとする。

9枚のコインを𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖とそれぞれ呼ぶこととし、量った結果に従い次の天秤での計 量を行うことを矢印で表すと、以下の図により3回の計量で偽物の判別と重い・軽いの判断が 可能である。

第 10 週

グラフ構造と最短路問題

アルゴリズムとデータ構造

8 ^2014/12/4 アルゴリズムとデータ構造

本日の到達目標と概要

• 到達目標

– グラフの基礎とそのデータ表現、また代表的な問題である最短 路問題を知る

• 概要

– グラフの基礎

– グラフのデータ表現 – 最短路問題

– Dijkstra のアルゴリズム

9 ^2014/12/4 アルゴリズムとデータ構造

グラフの定義（１）

• グラフ（ Graph ）

• 頂点（ Vertex ）の有限集合 V と辺（ Edge, Arc ）の有限集合 E により定 義

– 節（ Note ）、枝（ Branch ）とも

• グラフの図表現

– 集合表現

2014/12/4 アルゴリズムとデータ構造

10

グラフの定義

2014/12/4 アルゴリズムとデータ構造

11

グラフ（Graph） グラフ（Graph）

頂点（Vertex）の有限集合𝑉と辺（Edge, Arc）の有限集合𝐸によって定義され る。

𝐺 = 𝑉, 𝐸

頂点、辺はそれぞれ節（Node）、枝（Branch）とも呼ばれる。

グラフの図表現 グラフの図表現

：頂点

：辺

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝑐 𝑑

𝐺₁ = 𝑉₁, 𝐸₁ 𝑉₁ = 𝑎, 𝑏, 𝑐, 𝑑

𝐸₁ = 𝑎, 𝑏 , 𝑎, 𝑐 , 𝑏, 𝑐 , 𝑏, 𝑑 , 𝑐, 𝑑

𝐺₂ = 𝑉₂, 𝐸₂ 𝑉₂ = 𝑎, 𝑏, 𝑐, 𝑑

𝐸₂ = 𝑎, 𝑏 , 𝑎, 𝑐 , 𝑐, 𝑎 , 𝑐, 𝑏 , 𝑏, 𝑑 , 𝑐, 𝑑 無向

グラフ𝐺₁ 無向 グラフ𝐺₁

有向 グラフ𝐺₂

有向 グラフ𝐺₂

グラフの用語（１）

2014/12/4 アルゴリズムとデータ構造

12

有向グラフ（Directed Graph） 有向グラフ（Directed Graph）

無向グラフ（Undirected Graph） 無向グラフ（Undirected Graph）

辺が向きを持つグラフ（例：スライド11の𝐺₂）

辺が向きを持たないグラフ（例：スライド11の𝐺₁） 隣接（Adjacent）

隣接（Adjacent）

あるグラフ𝐺 = 𝑉, 𝐸 で𝑒 = 𝑢, 𝑣 で𝑒 ∈ 𝐸のとき、頂点𝑢と𝑣は互いに隣接して いる、と言う

有向グラフの場合、あるグラフ𝐺 = 𝑉, 𝐸 で𝑒 = 𝑢, 𝑣 で𝑒 ∈ 𝐸のとき、頂点𝑢は 𝑣に隣接すると言い、頂点𝑣は𝑢から隣接すると言う。

始点と終点 始点と終点

あるグラフ𝐺 = 𝑉, 𝐸 で𝑒 = 𝑢, 𝑣 で𝑒 ∈ 𝐸のとき、頂点𝑢を辺𝑒の始点、𝑣を辺𝑒 の終点と言う

グラフの用語（２）

2014/12/4 アルゴリズムとデータ構造

13

次数（Degree） 次数（Degree）

無向グラフにおいて、ある頂点に接続している辺の個数

有向グラフの場合は、ある頂点について、それを始点とする辺の個数をそ の頂点の出次数（Out-degree）、それを終点とする辺の個数をその頂点の 入次数（In-degree）という。

孤立（Isolated） 孤立（Isolated）

次数0の頂点を孤立しているという 完全グラフ（Complete Graph）

完全グラフ（Complete Graph）

どの2頂点をとってもそれらが隣接しているようなグラフ。

頂点の個数 𝑉 が𝑛の完全グラフを𝐾_𝑛と書く 部分グラフ（Subgraph）

部分グラフ（Subgraph）

𝐺^′ = 𝑉^′, 𝐸^′ があって、 𝑉^′ ⊆ 𝑉かつ𝐸^′ ⊆ 𝐸のとき 𝐺′は𝐺の部分グラフという

グラフの用語（３）

2014/12/4 アルゴリズムとデータ構造

14

誘導（生成）部分グラフ（Induced Subgraph） 誘導（生成）部分グラフ（Induced Subgraph）

グラフ𝐺 = 𝑉, 𝐸 に対して、 𝑉の部分集合𝑉′を考える。このとき、 𝐸^′ = 𝑢, 𝑣 ∈ 𝐸 | 𝑢, 𝑣 ∈ 𝑉′ を用いて作られる部分グラフ𝐺^′ = 𝑉^′, 𝐸^′ を、グラフ𝐺 の誘導（生成）部分グラフという

クリーク（Clique） クリーク（Clique）

グラフ𝐺の部分グラフで、しかも完全グラフであるものを𝐺のクリークと言 う。

𝐺のクリークのうち最も多くの頂点を含むものを最大クリークと言う。

グラフの用語（４）

2014/12/4 アルゴリズムとデータ構造

15

道（Path、路）

道（Path、路）

頂点列𝑃 = 𝑣₀, 𝑣₁, ⋯ , 𝑣_𝑘で 𝑣_𝑖, 𝑣_𝑖+1 ∈ 𝐸 𝑖 = 0, ⋯ , 𝑘 − 1 がなりたつもの 単純（Simple）

単純（Simple）

道𝑃に現れる頂点がすべて異なるとき、𝑃は単純であるという 閉路（Cycle、Circuit）

閉路（Cycle、Circuit）

𝑣₀ = 𝑣_𝑘のとき、𝑃を閉路という ループ（Self-loop）

ループ（Self-loop） 長さ1の閉路

到達可能（Reachable） 到達可能（Reachable）

2頂点間を結ぶ道が存在するとき、到達可能であるという

グラフの用語（５）

2014/12/4 アルゴリズムとデータ構造

16

最短路（Shortest Path） 最短路（Shortest Path）

到達可能な2頂点間を結ぶ長さ最小のものを最短路という 距離（Distance）

距離（Distance）

到達可能な2頂点間の最短路の長さを距離という。

到達可能でない2頂点の距離は無限大∞と定義する。

有向路（Directed Path） 有向路（Directed Path）

有向グラフのとき、 𝑣_𝑖, 𝑣_𝑖+1 ∈ 𝐸 𝑖 = 0, ⋯ , 𝑘 − 1 を満たすような頂点列 𝑃 = 𝑣₀, 𝑣₁, ⋯ , 𝑣_𝑘があるとき、𝑃を頂点𝑣₀から𝑣_𝑘へ至る有向路といい、𝑣_0か ら𝑣_𝑘へ到達可能という

描いてみる演習：グラフの描画

2014/12/4 アルゴリズムとデータ構造

17

𝐾₆を描画せよ

書いてみる演習：部分グラフ

2014/12/4 アルゴリズムとデータ構造

18

下のグラフに対し、 𝑉^′ = 𝑎, 𝑏, 𝑒 をつかった誘導グラフ を図示と集合の双方で示せ

𝑎 𝑏

𝑐 𝑑

𝑒

𝑓

𝑔 ℎ

𝑎 𝑏

𝑒 図示

図示

集合 集合

𝐺^′ = 𝑉^′, 𝐸^′ 𝑉^′ = 𝑎, 𝑏, 𝑒

𝐸^′ = 𝑎, 𝑏 , 𝑒, 𝑒

グラフの物理表現：順配置表現

2014/12/4 アルゴリズムとデータ構造

19

𝐴₁ =

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

𝐴₂ =

0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 隣接行列（Adjacency Matrix）

隣接行列（Adjacency Matrix）

行列𝐴の各行と各列を頂点に対応させ、行列の要素𝐴 𝑖, 𝑗 が、

無向グラフの場合 𝑖, 𝑗 ∈ 𝐸あるいは 𝑗, 𝑖 ∈ 𝐸ならば1、そうでないなら0と なっている行列。

有向グラフの場合 𝑖, 𝑗 ∈ 𝐸ならば1、そうでないなら0となっている行列。

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝑐 𝑑

無向 グラフ𝐺₁

無向 グラフ𝐺₁

有向 グラフ𝐺₂

有向 グラフ𝐺₂

隣接行列

隣接行列

グラフの物理表現：リンク配置表現（１）

2014/12/4 アルゴリズムとデータ構造

20

直交リスト 直交リスト

𝐴₂ =

0 1 1 0

0 0 0 1

1 1 0 1

0 0 0 0

𝑎 𝑏

𝑐 𝑑

有向 グラフ𝐺₂

有向 グラフ𝐺₂

• 最も左の1列と最も上の1行 はそれぞれ始点、終点とし ての頂点を表したレコード

• それ以外のレコードは辺を 表す

グラフの物理表現：リンク配置表現（２）

2014/12/4 アルゴリズムとデータ構造

21

隣接リスト 隣接リスト

𝑎 𝑏

𝑐 𝑑

𝑎 𝑏

𝑐 𝑑

無向 グラフ𝐺₁

無向 グラフ𝐺₁

有向 グラフ𝐺₂

有向 グラフ𝐺₂

• 最も左のレコード群が頂点を表 し、その頂点が隣接する頂点を リストとして持っている

グラフのアルゴリズム：最短路問題

2014/12/4 アルゴリズムとデータ構造

22

重み付グラフ（Weighted Graph） 重み付グラフ（Weighted Graph）

辺に距離などのコストが付いたグラフ

𝑆 𝐷

𝐴 𝐵

𝐻 𝐼

𝐸 𝐽

𝐶 𝐹 𝐾 𝐺

4

3

1

1

2

2 2

1 1

2

3

1 3

𝑆 からスタートして 𝐺 に至る道で、

コストの総和が最小になる道を見 つけるにはどうしたらよいか

𝑆 からスタートして 𝐺 に至る道で、

コストの総和が最小になる道を見 つけるにはどうしたらよいか

最短路問題

Dijkstra のアルゴリズム

2014/12/4 アルゴリズムとデータ構造

23

• 開始点からの集積コス トの増加が最も少ない 頂点を最優先する、と いう原則に従い、新た な頂点を1つずつ取り 込んでいく手法。

• グラフと始点とが与え られると、他の頂点ま での最短経路とコスト が求められる

Dijkstra アルゴリズムを用いた事例

2014/12/4 アルゴリズムとデータ構造

24

𝑆 𝐷

𝐴 𝐵

𝐻 𝐼

𝐸 𝐽

𝐶 𝐹 𝐾 𝐺

4 3

1

1 2

2 2

1 1

2

3 1 3

𝑉 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻, 𝐼, 𝐽, 𝐾, 𝑆}

cost[A] = w[S, A] = 3 cost[B] = ∞

cost[C] = ∞

cost[D] = w[S, D] = 4

（あとは∞。省略）

1番小さいコストの頂点を選ぶ Aが選ばれる

UからAが取り除かれる Aの隣接DA={S,B,C}

DA ∩ U = {B, C}

頂点Bに対して

cost[A]+w[A,B] ? cost[B]

3+1=4

＜

parent[B] = A 頂点Cにも

同じように行う

Dijkstra アルゴリズムを用いた事例

2014/12/4 アルゴリズムとデータ構造

25

𝑆 𝐷

𝐴 𝐵

𝐻 𝐼

𝐸 𝐽

𝐶 𝐹 𝐾 𝐺

4 3

1

1 2

2 2

1 1

2

3 1 3

𝑉 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻, 𝐼, 𝐽, 𝐾, 𝑆}

1番小さいコストの頂点を選ぶ Bが選ばれる

UからBが取り除かれる Bの隣接DB={A, E, F, K}

DB ∩ U = {E, F, K}

頂点Eに対して

cost[B]+w[B,E] ? cost[E]

4+2=6

＜

parent[E] = B cost[A] = 3

cost[B] = 4 cost[C] = 4 cost[D] = 4

（あとは∞。省略）

Floyd のアルゴリズム

2014/12/4 アルゴリズムとデータ構造

26

• グラフが与えられると、

2頂点間の最短経路と コストが求められる

演習（その 10 ）

2014/12/4 アルゴリズムとデータ構造

27

Floydのアルゴリズム Floydのアルゴリズム

演習：下のグラフに対し、Floydのアルゴリズムを適用した場合、最終的に出力 される配列costの情報を示せ

𝑆 𝐷

𝐴 𝐵 𝐸

𝐶

4 3

1

1 2

2

𝑉 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝑆}

S A B C D E

S 0 3 ∞ ∞ 4 ∞

A 3 0 1 1 ∞ ∞

B ∞ 1 0 ∞ ∞ 2

C ∞ 1 ∞ 0 ∞ ∞

D 4 ∞ ∞ ∞ 0 2

E ∞ ∞ 2 ∞ 2 0

配列costの初期状態 配列costの初期状態

演習（その 10 ）：実行イメージ

2014/12/4 アルゴリズムとデータ構造

28

> java Floyd Initial Phase

0, 3, inf, inf, 4, inf 3, 0, 1, 1, inf, inf inf, 1, 0, inf, inf, 2 inf, 0, inf, 0, inf, inf 4, inf, inf, inf, 0, 2 inf, inf, 2, inf, 2, 0 Final Phase

4, 3, 5, 10, 3, ,

＜省略＞

> java Floyd Initial Phase

0, 3, inf, inf, 4, inf 3, 0, 1, 1, inf, inf inf, 1, 0, inf, inf, 2 inf, 0, inf, 0, inf, inf 4, inf, inf, inf, 0, 2 inf, inf, 2, inf, 2, 0 Final Phase

4, 3, 5, 10, 3, ,

＜省略＞

ここに書いてある 値は適当です。

自分で解いてみましょう

本日の到達目標と概要

• 到達目標

– グラフの基礎とそのデータ表現、また代表的な問題である最短 路問題を知る

• 概要

– グラフの基礎

– グラフのデータ表現 – 最短路問題

– Dijkstra のアルゴリズム

29 ^2014/12/4 アルゴリズムとデータ構造

締切と提出方法：演習その 10

• 締切

– 2週間後（12月18日）の16:10まで

• 提出方法

– 電子メール

• メールアドレス

– [email protected]

– メールのタイトルに「アルゴリズムとデータ構造第5回課題」と書 いてください

– 作ったプログラムをメールに添付してください。

• 注意事項

– 必ず金岡から受領確認メールを返します。

• 必ず日本語で受領確認メールを返します

• 英語のメールはエラーメール（アドレスが間違っている）の可 能性が高いです

– メールで提出がされていないものは未提出とみなします

2014/10/30 アルゴリズムとデータ構造

30