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

1
アルゴリズムとデータ
構造
第１０回グラフとネットワークのアルゴリズム(1)
2015/12/16
アルゴリズムとデータ構造 2015
2
グラフとネットワーク
グラフ(graph)とは
頂点(vertex)の集合Vと辺の集合E⊆V×Vの組(V,E)
無向グラフ
(undirected graph)
v0
e0
e5
v1
v4
e2
e4
e1
v e3 v
2
有向グラフ
(directed graph)
v0
e0
e5
v1
v4
e2
e1
e4
e0=(v0,v1), e1=(v1,v2), e2=(v0,v2),
e3=(v2,v3), e4=(v3,v4), e5=(v4,v0)
辺(u,v)は有向グラフの場合、
頂点uから頂点vへの辺を表す。
v2 e3 v3
3
V={v0,v1,v2,v3,v4,v5}
E={e0,e1,e2,e3,e4,e5}
重み付きグラフ(weighted graph,ネットワーク(network))とは
各辺に重み（整数値または実数値）が付いたグラフ
2
2
4
3
2015/12/16
2
2
2
1
4
3
2
1
無向グラフでは
辺(u,v)を{u,v}と
書く場合もある。
アルゴリズムとデータ構造 2015
隣接行列と隣接リスト
3
v0
v0
V={v0,v1,v2,v3,v4,v5}
v1
E={(v0,v1),(v1,v2),(v0,v2),
(v2,v3),(v3,v4),(v4,v0)}
v4
2
v1
2
v4
4
3
v2
頂点の数をn、辺の数をmとする。
v3
1
v2 2 v3
隣接行列(adjacency matrix)
v0
v1
v2
v3
v4
v0
0
0
0
0
1
v1
1
0
0
0
0
v2
1
1
0
0
0
v3
0
0
1
0
0
v4
0
0
0
1
0
1 ((vi,vj)∈E)
A(i,j)=
0 ((vi,vj)∈E)
利点・２頂点間に辺があるか否かを
O(1)時間でチェック可能
欠点・O(n2)の記憶領域が必要。
・１つの頂点の隣接頂点をすべて
求めるのにO(n)時間必要。
v0
v1
v2
v3
v4
v0
0
0
0
0
2
v1
2
0
0
0
0
v2
4
3
0
0
0
v3
0
0
2
0
0
v4
0
0
0
1
0
隣接リスト(adjacency list)
1 2
2 4 NULL
利点・O(m)の記憶領域で済む。
0
NULL
2 3 NULL
・１つの頂点の隣接頂点を全て求める
1
NULL
3 2 NULL
のに、その頂点の隣接頂点数の定数
2
NULL
4 1 NULL
倍時間で可能。
3
NULL
0 2 NULL
欠点・２頂点間に辺があるか否かをチェック
4
するのに隣接頂点の数のオーダーの
時間が必要
無向グラフの場合は、各辺が両方向の２辺からなる有向グラフとして隣接行列、隣接リストを作成すればよい。
0
1
2
3
4
2015/12/16
1
2
3
4
0
2
NULL
アルゴリズムとデータ構造 2015
無向グラフの探索
4
連結無向グラフのすべての頂点を訪れる探索法には主に次の２つがある。
１．深さ優先探索(Depth-First Search, DFS)
２．幅優先探索(Breadth-First Search, BFS)
v０
[深さ優先探索のアルゴリズム]
Step 1 vの状態←未訪問 for all v∈V
Step 2 v0←適当な頂点(出発点)
Step 3 dfs(v0)を実行
dfs(v:頂点)
Step 1 vの状態←訪問済
Step 2 vの全ての隣接頂点uに対して以下のことを行う。
if uの状態=未訪問 then dfs(u)を実行
[幅優先探索のアルゴリズム]
Step 1 vの状態←未訪問 for all v∈V
Step ２適当な頂点v0(出発点)をキューqに入れる
v0の状態←訪問済
Step ３ if qが空 then 停止
Step ４ qから頂点を１つ取り出してそれをvとする。
Step ５ vの全ての隣接頂点uに対して以下のことを行う。
if uの状態=未訪問 then
uの状態←訪問済
uをqに入れる
end if
Step ６ Step ３へ戻る
2015/12/16
v1
v7
v2
v5
v3
v6
v4
q v42376510 v26375 v2763 v237 v2
v０
v1
v7
v2
v5
v3
v6
v4
最悪/平均時間計算量O(n+m)
(n:頂点数、m:辺の数)
アルゴリズムとデータ構造 2015
最小スパニング木
5
グラフG’はグラフG=(V,E)のスパニング木（全域木、spanning tree)
def
⇔G’はGのすべての頂点を含む部分グラフ(V,T)で木になっているもの
def
（グラフGは木 ⇔ Gは閉路のない連結無向グラフ）
深さ優先のスパニング木（太線）
幅優先のスパニング木（太線）
v０
v1
v1
v7
v7
v2
v2
v3
v０
v4
v5
v6
v3
v4
v5
v6
グラフG’は重み付きグラフG=(V,E)の最小スパニング木(minimum spanning tree)
def
⇔Gのスパニング木で、含まれる辺の重みの総和が最小のもの
G
1
2
2
3
最小スパニング木を求めるアルゴリズム
Gの最小スパニング木 1
5
クラスカル(Kruskal)のアルゴリズム
2
4
2
4
7
応用として、通信網の設計、ガス・水道の配管等がある。
2015/12/16
プリム(Prim)のアルゴリズム
最悪時間計算量： O(m log n)
(n: 頂点数, m: 辺の数)
アルゴリズムとデータ構造 2015
6
クラスカルのアルゴリズム
[考え方] 重みが小さい辺から選択していく。ただし、選択することに
より閉路ができる場合は選択しない。
Joseph B. Kruskal
1928-2010 , USA
[例]
①
G 1
2
②
辺の重み
①
1
⑥
5
3
④
7
⑦
2
③
1
5
2
4
⑤
2
3
7
1
5
2
4
2
②
3
4
7
2
1
5
3
7
2
③
5
2
4
2
3
7
辺の重みの順位
[アルゴリズム]
Step 1 T←φ
Step 2 辺の配列eを重みの小さい順に整列
Step 3 i=0,1,…,m-1の順で次のことを行う。
if T∪{e[i]}は閉路を含まない then T←T∪{e[i]}
2015/12/16
アルゴリズムとデータ構造 2015
4
⑤
7
クラスカルのアルゴリズムのベースとなる補題
次の補題が成り立つ。
E−T(または
E＼Tとも表
記)は集合
間の演算で
EからTに含
まれる要素
を除いた集
合
補題 (V,E)を連結無向グラフとし、T⊆Eとする。このとき、以下の条件は部分
グラフ(V,T)が(V,E)の最小スパニング木であるための必要十分条件である。
条件部分グラフ(V,T)は(V,E)のスパニング木で、全てのe∈E－Tに対して
w(e)≧w(e’) for all e’∈CT(e)
ただし、w(e)は辺eの重みを表し、CT(e)は辺e∈E－TとTの辺によって作られ
る閉路に含まれるTの辺の集合を表すものとする。
e
e
G
1
1
5
2
2
3
4
2015/12/16
2
3
7
細線:E−T
1
5
2
7
太線:T
1
5
5
2
4
2
3
2
4
7
2
3
7
4
e
黄色線:CT(e)
アルゴリズムとデータ構造 2015
8
クラスカルのアルゴリズムが正しいことの証明
（証明）
クラスカルのアルゴリズムにより求めた辺の集合をT0とする。このとき、補題の条件が
成り立っていることを示せばよい。
v
まず、(V,T0)がスパニング木であることを示す。(V,T0)は明らかに閉路を持たない。
いま、T0に含まれる辺の端点の集合をV’とし、V’=Vを示す。
u
V’
V’≠Vとすれば、ある頂点v∈V－V’が存在する。(V,E)は連結であるので、ある
頂点u∈V’が存在して、V’の頂点を経由しないでvへ到達する路が存在する。
その路に属する辺をT0に加えても閉路はできない。これはアルゴリズムの
e
CT0(e)
「閉路ができない限り辺を加える」という動作に矛盾する。
’
e
よってV’=Vとなり、(V,T0)はスパニング木であることが示された。
w(e)<w(e’)
次に、全てのe∈E－T0、全てのe’∈CT0(e)に対してw(e)≧w(e’)が成り立つことを示す。
あるe∈E－T0が存在して、あるe’∈CT0(e)に対してw(e)<w(e’)が成り立ったとする。
すると、アルゴリズムのStep 3においてT∪{e}が閉路を持つか否かチェックしたときには、
Tにはe’は含まれていないので、T∪{e}は閉路を持たないことになりT0がeを含んでいな
いことに矛盾する。
よって全てのe∈E－T0、全てのe’∈CT0(e)に対してw(e)≧w(e’)が成り立つことが示された。
（証明終り）
2015/12/16
アルゴリズムとデータ構造 2015
9
補題の証明
（証明）
（⇒） (V,T)が最小スパニング木なのに条件を満たさないと仮定する。すると
e
あるe∈E－Tが存在し、あるe’∈CT(e)に対してw(e)<w(e’)が成り立つ。
CT0(e)
(V,T∪{e}－{e’})は(V,E)のスパニング木であり、(V,T)よりも辺の重みの和が ’
e
小さい。これは(V,T)が最小スパニング木であることに矛盾する。よって、
w(e)<w(e’)
(V,T)が最小スパニング木であれば、条件を満たす。
（）最小スパニング木の１つを(V,T*)とする。条件を満たす(V,T)の辺の重みの和
は(V,T*)の辺の重みの和に等しいことを示す。e∈T*－Tが存在したとする。
eにより分かれる２つの連結成分を（V0,T*0),(V1,T*1)とすると、e’∈CT(e)で
２つの連結成分（V0,T*0),(V1,T*1)を跨ぐ辺e’∈Tが存在する。(V,T)は条件
を満たしているのでw(e)≧w(e’)が成り立つのでT’=T*∪{e’}－{e}とすれば、
T’の重みの総和はT*の重みの総和以下になる。T*は最小スパニング木なので、
T’もT*と重みの総和が等しい最小スパニング木であり、|T’－T|<|T*－T|を満たす。
ただし、|S|は集合Sの要素数を表すものとする。したがってT’をT*として同じ
操作を繰り返すとT’=Tとなり、TもT*と重みの総和が等しい最小スパニング木で
あることが示される。
（証明終り）
2 e’
T
T*
2015/12/16
3
e 2
3
2
2
3
e’
3
e
3
アルゴリズムとデータ構造 2015
10
T∪{e}が閉路を含むか否かを効率的にチェックする方法
[考え方] 頂点の集合Vをグラフ
(V,T)において連結している成
分に分解した場合に、eの両端
が同じ成分に属している（閉路
を含む）か否（閉路を含まな
い）かをチェックする。
両端が同じ成分に属している
→加えると閉路を含むグラフになる
両端が異なる成分に属している
→加えても閉路を含むグラフにならない
頂点集合Vをグラフ(V,T)の連結成分に分割することによりできる集合族S0,S1,…,Skを
保持し、次の２つの手続きを用意する。
find(a) : a∈Siと成るような集合Siの名前を返す。
union(ID0,ID1) : 名前がID0, ID1である集合SiとSjを統合して１つの集合にする。
e[i]=(e[i].from,e[i].to)とすれば、上の２つの手続きを使ってStep 3 は次のように書ける。
Step 3 i=0,1,2,…,m-1の順で次のことを行う。
ID0←find(e[i].from)
ID1←find(e[i].to)
if(ID0≠ID1) then
T←T∪{e[i]}
union(ID0,ID1)
end if
2015/12/16
アルゴリズムとデータ構造 2015
11
集合族のfind, unionに適したデータ構造
それぞれの集合を、要素(頂点ID)を節点のラベルとする木で表現し、
根のラベルを集合の名前とする。
名前が7の連結成分
[例]
0
②
1
7
0
③ ④ ①
2
5
3
⑦
⑥
6
4
⑤
名前が2の連結成分
find(i) : ラベルiの節点から親を辿り根のラベルを返す
Union(i,j) : ラベルiとラベルjを根に持つ木をマージする。ただし、高さが低い方
の木の根を高い方の木の根の子とする。（高さが同じ場合はどちらでもよい）
最悪時間計算量
find: O(log n) (n:要素数)
union: O(1)
2015/12/16
②
Union(2,7)に統合された木
③ ④ ①
⑦
⑤ 0
⑥
アルゴリズムとデータ構造 2015
12
find(i)の最悪時間計算量がO(log n)であることの証明
集合族のfind(i)の時間計算量は、ラベルiの節点の深さに比例するので、
根のみのn個の木から出発してunionを何度か繰り返し適用した場合、作成される
任意の木の高さkはlog2n以下であることを示せばよい。
これには以下のことを示せばよい。
unionにより作られる高さkの木は節点数が2k以上 ---------------------------①
なぜならば、①が成り立つのに高さがlog2nより大きいとすると節点数がn=2log2nよ
り大きいことになり矛盾するからである。
①を数学的帰納法で証明する。
k=0のときは高さが０の木の節点数は１であるから①は成り立つ。
k=h(h≧0)のとき①が成り立つと仮定する。
k=h+1の木Tの根のラベルをiとする。根のラベルがiの木の高さがh+1になったの
はラベルiの木の高さがhのとき、高さhの木をマージしたunionを行った場合であり、
それ以外はあり得ない。このとき、高さk=hの木に対しては①が成り立つという仮
定から、マージ後の木の節点数は2・2h=2h+1以上となる。Tは、その後unionを何度
か適用された木かもしれないが、unionにより節点数は増えるだけなので、Tの節
点数も2h+1以上である。
したがって、k=h+1のときにも①が成り立つ。
（証明終り）
2015/12/16
アルゴリズムとデータ構造 2015
13
クラスカルのアルゴリズムの最悪時間計算量はO(m log n)
(証明)
Step 1は定数ステップ。
Step 2はm個のソートなのでO(m log m)であるが、m≦n2なのでO(m log n)。
Step 3はn-1回のunionと高々2m回のfindを実行するからO(n+m log n)。
連結グラフで考えているのでn-1≦mであるからStep 3はO(m log n)で実行できる。
したがって全体でもO(m log n)で実行できる。
（証明終り）
2015/12/16
アルゴリズムとデータ構造 2015

Download Report