ソフトウェア工学

８．任意のデータ構造
（グラフの表現とアルゴリズム）
• ８－１．グラフの数学的定義
• ８－２．配列でのグラフ表現
– 隣接行列
– 接続行列
• ８－３．隣接リスト表現
• ８－４．グラフ上のアルゴリズム
1
８－１．グラフの数学的表現
 n個の頂点の集合を
V = {v1, v2 , L , vn }
とし、
 ｍ個の辺の集合を
E = {e1, e2 , L , em }
とする。ただし、辺 ei Î E は、
頂点の対、すなわち ei = (vp , vq ) Î V ´ V と表せる。
よって、 E Í V ´ V
である。
 このとき、グラフ G は頂点集合V と辺集合E
の対 G = (V , E )で表される。
2
グラフの図式表現
辺
v7
v1
e1
v2
e4
e2
e3
v3
V = {v1, v2 , L , v7 }
G = (V , E )
e8
v4
頂点
e7
e6
v6
e5
v5
E = {e1 , e2 , L , e8 }
= {(v1 , v2 ), (v2 , v 3 ), L , (v 7 , v 4 )}
3
練習
（１）
図式表現で与えられた次のグラフの
（集合による）数学的表現を与えよ。
（２）次の数学的表現で与えられたグラフの図式表現を
求めよ。
E = {e1, e2 , e3 , e4 , e5 , e6 , e7 , e8 }
G = (V , E )
V = {v1, v2 , v 3 , v 4 , v5 , v6 }
= {(v1, v2 ), (v1, v 3 ), (v1, v 4 ), (v1, v6 ),
(v2 , v 3 ), (v 3 , v 4 ), (v 4 , v5 ), (v5 , v6 )}
4
８－２．配列でのグラフ表現
• 配列（行列）でグラフを表現する方法には
主に２つの方法がある。
– 隣接行列点同士の隣接関係に注目する方
法
– 接続行列点と辺の接続関係に注目する方
法。
5
隣接と接続
e1 はv 1
に
接続している。
v1
e4
e1
v2
e2
v7
v3
e3
e8
v4
v 6 と v7
は
隣接している。
e7
e6
e5
v6
v5
v
点 i と点v j に対して、 (vi , v j ) Î E であるとき、
その２点は隣接している。
点 v i と辺e j に対して、e j = (vi , vk ) であるとき、
辺 e j は点 v i に接続している。
6
隣接行列
v1
v2
v7
v4
v3
v6
v5
v1 v 2
v3
v4
v5
v6
v7
v1
0
1
0
1
0
0
0
v2
1
0
1
0
0
0
0
v3
0
1
0
1
0
0
0
vv
1
0
1
0
1
1
1
v5
0
0
0
1
0
0
0
v6
0
0
0
1
0
0
1
v7
0
0
0
1
0
1
0
無向グラフの隣接行列は、対称行列。
7
隣接行列の性能
n:頂点数V 、
m:辺数 E とする。
記憶量
O(n 2 )
領域
２点間の隣接関
係チェック
O (1)
時間
１点からの隣
接関係チェック
O (n )
時間
8
接続行列
e1 e2 e 3 e 4 e5 e6 e 8 e9
v1
v7
e7
e
e4 8
e1
v4
v6
v2
e6
e 2 v3 e 3 e 5
v5
v1
1
0
0
1
0
0
0
0
v2
1
1
0
0
0
0
0
0
v3
0
1
1
0
0
0
0
0
v4
0
0
1
1
1
1
0
1
v5
0
0
0
0
1
0
0
0
v6
0
0
0
0
0
1
1
0
v7
0
0
0
0
0
0
1
1
9
接続行列の性能
n:頂点数V 、
E とする。
m:辺数
記憶量
O (nm ) 領域
接続関係のチェッ
ク
１点からの隣
接関係チェック
2
m = O(n )
O (1)
O(m )
にも注意する。
時間
時間
10
練習
図式表現で与えられた次のグラフの
（１）隣接行列およびせ接続行列を与えよ。
11
８－３．隣接リスト表現
• 隣接行列では、隣接関係にないものまで
保存していた。
• この無駄をリスト構造によって、解消する。
12
隣接リスト
v1
v2
v7
v4
v3
v1
v2
v3
v 6 v4
v5
v
v5 6
v7
v2
v1
v2
v1
v4
v3
v4
v3
v4
v4
v4
v7
v6
v5
v6
v7
13
隣接リストの性能
n:頂点数V 、
E とする。
m:辺数
記憶量
O (n + m )
２点間の隣接関
係のチェック
O (D )
１点からの隣
接関係チェック
O (D )
D : 最大次数
D = O (n ) にも注意する。
領域
時間
時間
14
練習
（１）
図式表現で与えられた次のグラフの
隣接リストを与えよ。
15
８－４．グラフ上のアルゴリズム
• グラフの表現法により、アルゴリズムの計
算量に差が生じる。
– →問題やその解法（アルゴリズム）にしたがっ
て、表現法を選択する必要がある。
• グラフ上の基本的探索技法
– 深さ優先探索とスタック
– 幅優先探索とキュー
16
グラフ探索アルゴリズム
1. 始点ｓを選び、ラベルＬ＝１にセットする。
① ｓにラベルＬをつける。
② ｓの隣接点を集合Ｓに入れる。
2. 集合Ｓから一点ｐを取り出す。
① Ｌ＋＋とし、ｐにラベルＬをつける。
② ｐの隣接点でラベルがついていないものを、集
合Ｓに入れる。
3. 全ての点にラベルがつくまで、２．を繰り返す。
17
深さ優先探索(Depth First Search)
dfs(vertex v){
stack s;
L=1;
while(L<n){
Label[v]=L;
for(vの隣接リストlist[v]）｛
w Î list [v ] が未ラベルなら、
s.push(w);}
v=s.pop();
L++:
}
}
18
ＤＦＳの動作
v2
１v1
v3
v2
v7
v4
２
v3
v
v2
v6
v5
v4
v6
v5
１ 1
v3
v7
１v1
v7
v4
１ 1
２
v4
v3
v2
v4
v7
v
v2
v6
v5
v4
v6
v5
v3
v4
19
v7
v
v2
１ 1
２
v3 ３
v4
１ 1
２
v3 ３
v
v2
v4
v4
４
v6
v5
１ 1
２
v3 ３
v7
v
v2
v6
v5
v7
v4
４
v7
v
v5
v6
v7
v2
１ 1
２
v3 ３
v6
v5
v4
４
v6
v5
５
v6
v7
20
v2
v7
１v1
２
v3 ３
v4
４
v
６
6
v
v5
５
v2
１ 1
２
v7
v3 ３
v
７ 7
v4
４
v6
v5
６
５
21
幅優先探索(Bepth First Search)
bfs(vertex v){
queue q;
L=1;
while(L<n){
Label[v]=L;
for(vの隣接リストlist[v]）｛
w Î list [v ] が未ラベルなら、
q.enqueue(w);}
v=q.dequeue();
L++:
}
}
22
ＢＦＳの動作
v2
１v1
v3
v2
v7
v4
v3
v
v2
v6
v5
v7
v4
２
v6
v5
v2
１ 1
v3
v2
１v1
v7
v4
v
v2
v3
v4
２
v4
v6
v5
v7
１ 1
v2
v6
v5
v3
v5
v6
v7
v2
23
v7
v
v2
１ 1
３
v3
v4
２
v7 ４
v
v2
１ 1
３
v3
v6
v5
v4
２
v6
v5
v3
v5
v6
v7
v
v2
１ 1
３
v3
v3
v5
v6
v7
v4
２
１ 1
３
v3
v6
v5
v7 ４
v
v2
v3
v5
v6
v4
２
v6
v5
５
v3
v5
24
v7 ４
v
v2
１ 1
３
v3
v4
２
５
6
v
v 5６
v7 ４
v
v3
v2
３
１ 1
v 3７
v4
v 6５
v5
２６
25
グラフ探索アルゴリズムの性能
すべての辺をしらべながら、全ての頂点を訪れるので、
いかの計算量で実現可能である。
深さ優先探索
幅優先探索
時間計算量
領域計算量
O (n + m )
O (n )
O (n + m )
O (n )
n:点数、m:辺数
26

Download Report