p - 茨城大学

アルゴリズムとデータ構造
講義スライド 4
木
 グラフ
茨城大学工学部知能システム工学科井上康介
E2棟801号室
木とは
 リスト構造では枝分かれは起こらなかった．枝分かれしな
がらデータが伸びていくデータ構造を木 (tree) と呼ぶ．
 木はノード (node) とそれらを結ぶ枝 (branch) から構成
される．データが記録されているのはノードであり，枝は
データとデータの間の親子関係を示す．
A
ノード
B
D
G
p.276-277
枝
C
E
F
H
2
木とは
 あるノードから下に分岐した先のノードを子，分岐元の
ノードを親という．
 木の一番最初のノードを特に，根 (root) と呼び，子を持
たないノードを葉 (leaf) と呼ぶ．
根
A
親
子
D
B
親
子
C
E
F
子
G
H
葉
3
木とは
 あるノードから下につながった木構造の全体を部分木
(subtree) という．
 根からあるノードに到達するまでに通る枝の数をそのノー
ドの深さ (depth) といい，根から最も深いノードまでの
深さを木の高さ (height) という．
A
部分木
B
D
深さ 3
G
深さ 0
C
E
H
深さ 1
F
深さ 2
この木の高さ＝ 3
4
木とは
 ノードからの分岐が2以下の木を2分木 (binary tree) と呼
ぶ．
 親と子の関係が，ある規則 (大きい，小さいなど) に従っ
て並べられている木を2分探索木 (binary search tree) と
いう．
48
A
32
B
26
D
11
G
59
C
51
E
29
H
2分木
67
F
I
左の子 ≦ 親 ≦ 右の子
5
木とは
 木構造はきわめて重要で，多くの実用的対象が存在する．
 組織データやファイルシステムなどの階層構造の表現
 AI における論理的関係性の表現
 探索を容易にする情報表現 (2分探索木など)
 ヒープ・ソート
 講義では，2分探索木およびヒープに重点を置いて解説す
る．
6
2分探索木の配列表現
 ノードに格納するデータが人名であるとき，名前を辞書順
に並べる2分探索木が作れる．
 全ての親と子の間に，左の子≦親≦右の子という関係が成
立する．
右側の子のノード番号
No.0
1
Machilda
No.1
3
2
No.2
Candy
No.3
4
No.4
6
Ann
No.6
5
Rolla
No.5
Emy
7
Nancy
No.7
Eluza
Lisa
このようにノード番号を管理すれば，配列に格納できる．
p.278-282
7
2分探索木の配列表現
 各ノードに格納する情報は，人名，左の子へのポインタ
(ノード番号)，右の子へのポインタ (ノード番号) の3つで
ある．
 これを構造体にまとめ，配列にする．
struct tnode {
int left;
char name[64];
int right;
} a[100];
// 左部分木へのポインタ(番号)
// データ(人名)
// 右部分木へのポインタ(番号)
8
2分探索木の配列表現
 この配列を使って，2分探索木を表現できる．
 ただし，nil はポインタが指し示すものがないという意味
で，具体的には -1 などを使う．
a[p].left a[p].name a[p].right
0
1
2
3
No.0
1
Machilda
2
No.1
3
No.2
Candy
No.3
4
5
No.4
Ann
6
No.6
No.5
Emy
7
Nancy
No.7
Eluza
Lisa
Rolla
4
5
6
7
1 Machilda 2
3
Candy
4
5
Rolla
nil
nil
Ann
nil
6
Emy
7
nil
Nancy
nil
nil
Eluza
nil
nil
Lisa
nil
二分探索木の配列表現
9
2分探索木の配列表現
 2分探索木から key という目的データを探すには，root
から初めて，key がノードのデータより小さいときは左側
の木へ, 大きいときは右側の木へ探索すればよい．
実質的に二分探索 O(log n) の計算量
a[p].left a[p].name a[p].right
0
1
key が Eluza の場合
2
3
No.0
1
Machilda
2
No.1
3
No.2
Candy
No.3
4
5
No.4
Ann
6
No.6
No.5
Emy
7
Nancy
No.7
Eluza
Lisa
Rolla
4
5
6
7
1 Machilda 2
3
Candy
4
5
Rolla
nil
nil
Ann
nil
Emy
7
6
nil
Nancy
nil
nil
Eluza
nil
nil
Lisa
nil
二分探索木の配列表現
10
二分探索木の配列表現 (ソースコード)
 p.279
 このコードでは，2分探索木を初期化において与えてい
る．
 nil は -1 と定義 (プリプロセッサ)．
 scanf() で key を読み込み，p を 0 (根ノード) で初期
化．
 p が nil にならない限り続けるループに入る．
 strcmp() を使って，今見ているノード p の名前欄と
key を照合し，合致していたら発見したことを表示して
ループを抜ける．
 もし key の方が小さいときは，p を a[p].left に．
 逆の場合は p を a[p].right にする．
11
2分探索木へのデータの追加
 先程の例では，最初から 2分探索木ができていたが，これ
を作るアルゴリズムが必要
 すでに存在する 2分探索木に対して，新しいノードを追加
する手順は，以下の 2段階を踏む
 新ノードの親となるノードを探索
 新ノードを親ノードに接続
 現在調べているノードの番号を視点 p とし，この視点に一
つ遅れで追従する視点 old も用意する
 p を進めていき，p が nil になったとき，old が指し示し
ているノードが新ノードの親
12
2分探索木へのデータの追加
 p=0;
while (p!=nil){
old=p;

if (strcmp(key,a[p].name)<=0)
p=a[p].left;

else
p=a[p].right;

}





a[sp].left=a[sp].right=nil;
strcpy(a[sp].name,key);
if (strcmp(key,a[old].name)<=0)
a[old].left=sp;
else
a[old].right=sp;
sp++;
sp: 3
4
5
key: “Nancy”
“Patie”
p: -1
p old
0
1
Machilda
1
-1
2
p old
2
Candy
-1
-1
3
-1
p old
3
-1
Rolla
Nancy
-1
4
4
-1
Patie
-1
13
2分探索木の動的表現
 リストの場合と同様，ツリーもノードが動的に追加される
データ構造である．
 従って，自己参照構造体としてノードを表現し，必要に応
じてメモリを動的に確保するのが適している．
struct tnode {
struct tnode *left; /* 左部分木へのポインタ */
char name[12];
/* 名前 */
struct tnode *right; /* 右部分木へのポインタ */
};
struct tnode *talloc(void)
{
return (struct tnode *)malloc(sizeof(struct tnode));
};
p.283-284
14
新規ノード作成手順 (コードを見つつ)
 配列表現の時と同様，(1) 新規ノードの親となるノードの
探索，(2) 新規ノードの生成と親ノードからの接続を行う.
Candy を追加
Emyを追加
 視点 p を root で初期化．
p:NULL
 p は新規データ dat の大小にした
p=p->left
がって木をたどり，old は一つ遅れ
p old
Machilda
で追従：old=p としてから p を
old->left=p
適切な方向へ進める
p old
p=p->right
Candy
 p が NULL なら old が親ノード
old->right=p
p
 p=talloc()としてデータ記入
Emy
 左右の子はいない：NULL に
 親ノードの名前と新ノードの名前の大小関係により，
親ノードの左右どちらかのポインタを p に向ける
15
2分探索木の動的表現 (ソースコード)
 まずはルートノード作成
root=talloc();
scanf("%s",root->name);
root->left=root->right=NULL;
root
Machilda
16
2分探索木の動的表現 (ソースコード)
 while (scanf("%s",dat)!=EOF){
 p=root;
 while (p!=NULL){
 old=p;
 if (strcmp(dat,p->name)<=0)
 p=p->left; ここから下，p は
else
「視点」ではなく，
 p=p->right; 「新規ノード位置」
}
を示す．
 p=talloc();
 strcpy(p->name,dat);
 p->left=p->right=NULL;
 if (strcmp(dat,old->name)<=0)
 old->left=p;
else
 old->right=p;
}
 第2ノード以降作成
(さきほどの手順)
root
dat: Rolla
Nancy
p: NULL
p old
Machilda
p old
Rolla
p
Nancy
17
2分探索木の再帰的表現
(集中して聞くこと)
 木構造は再帰的処理に向いている．例えば探索の場合…
 「rootノード (Machilda) 以下から Emy を探す」と
いう問題は，「root->left (Candy) 以下の部分木から
Emy を探す」という副問題に分解できる．
root
この中からの探索
この中か
らの探索
再帰の脱出条件：
発見 or
行き先が NULL (不在)
(例：Eluza)
Machilda
Rolla
Candy
Ann
p.285-288 (途中まで)
Emy
18
ノード追加の再帰的方法
(集中して聞くこと)
 既存の 2分探索木に新しいデータ w を含むノードを追加す
る処理を再帰的に記述することを考える．
 再帰関数のプロトタイプを以下の通りとする：
struct tnode *gentree(struct tnode *p, char w[])
 p：起点ノード (このノード以下が作業対象)
 w：追加するデータ (名前)
 その動作は条件により異なる：
 p が NULL ではないとき：ノード p の適切な方の子
ノードを起点として gentree()を再帰呼び出しし，
受け取ったポインタ p をそのまま返す (オウム返し)
 p が NULL のとき：新規ノードを作り，w を格納，
作った新規ノードへのポインタを返す
19
ノード追加の再帰的方法
※ ここでは，データ Nancy を含むノードへの
ポインタを [Nancy] と表記する．
root
main()
root = gentree(root,”Emy”)
呼出
Nancy
[Nancy]
第 1引数が NULL 以外：
・適切な子を起点とする
再帰呼び出し
・第一引数をオウム返し
第 1引数が NULL ：
・新規ノードを作成
・新規ノードへのポイ
ンタを返す
gentree([Nancy],”Emy”) 同じポインタを上書き
 元の構造を壊さない
[Nancy]->left =
gentree([Nancy]->left,”Emy”);
呼出
[Candy]
gentree([Candy],”Emy”) NULL
Candy
[Candy]->right =
gentree([Candy]->right,”Emy”);
呼出
Emy
[Emy]
gentree(NULL,”Emy”)
ノード作成
戻り値の利用方法
に注目
20
ノード追加の再帰的方法
同じ方法で，第一ノード (root ノード) 作成も
できるだろうか？
root
main()
root = gentree(root,”Nancy”)
呼出
[Nancy]
第 1引数が NULL 以外：
・適切な子を起点とする
再帰呼び出し
・第一引数をオウム返し
第 1引数が NULL ：
・新規ノードを作成
・新規ノードへのポイ
ンタを返す
gentree(NULL,”Nancy”)
Nancy
・ノード作成
・作ったノードへのポインタを返す
第一ノード作成もそれ以降も
root = gentree(略) でOK！
 二分探索木の生成は，
root を NULL で初期化し，
root = gentree(略); を
繰り返せば全部できる！
void main(void)
{
char dat[12];
struct tnode *root;
}
root = NULL;
while (scanf("%s",dat)!= EOF){
root = gentree(root,dat);
}
21
ノード追加の再帰的方法 (ソース)
struct tnode *gentree(struct tnode *p, char *w)
{
if (p == NULL){
p = talloc();
新規ノード作成
strcpy(p->name, w);
p->left = p->right = NULL;
 p：新規ノード
}
else if (strcmp(w, p->name) < 0)  適切な子の選択
p->left = gentree(p->left, w);
再帰
else 子ポインタへの代入
再帰呼出
呼出
p->right = gentree(p->right, w);
return p;
 p：第一引数そのまま
}
ポインタを返す
(新ノードを作ったときはそれへのポインタ，そうでないときは
受け取った第一引数 p を (いじらずそのまま) オウム返し)
22
2分探索木のサーチ (再帰版)
while (printf("Search name -->"),
scanf("%s",key)!=EOF){
if ((p=search(root,key))!=NULL)
p=search(root,key))
printf(“%s
printf("%s が見つかりました\n”,p->name);
が見つかりました\n",p->name);
else
printf("見つかりません\n");
printf(“見つかりません\n”);
}
key: “Nancy”
“Rolla”
p
struct tnode *search(struct tnode *p,char *key)
struct tnode *search(struct tnode *p,char *key)
*p,char
*key)
{ struct tnode *search(struct tnode (p:
マチルダ)
{
(p:
ローラ)
(p: NULL)
{if (p==NULL || strcmp(key,p->name)==0)
if (p==NULL || strcmp(key,p->name)==0)
if
(p==NULL
return
p; || strcmp(key,p->name)==0)
return p;
return p;
if (strcmp(key,p->name)<0)
if (strcmp(key,p->name)<0)
if
(strcmp(key,p->name)<0)
return
search(p->left,key);
return search(p->left,key);
elsereturn search(p->left,key);
else
else
return search(p->right,key);
return search(p->right,key);
return search(p->right,key);
}
}
}
Machilda
p
Rolla
p: NULL
27
2分探索木のトラバーサル (深さ優先)
 トラバーサル (traversal)：木の全てのノードを訪れるこ
と (木の走査) (例：大学組織データ内からの教員捜し)
 深さ優先探索：「左向きにとにかく進んで，端に来たら 1
つ前の親に戻って右に進む」という行動を繰り返す．
 再帰的に記述すると，関数 treewalk(p)は，以下のよう
な動作をすれば良い (p：起点ノードへのポインタ)
void treewalk(struct tnode *p)
{
 p が NULL なら戻る (終了条件)
if (p!=NULL){
 p の左の子を起点として再帰呼出
treewalk(p->left);
printf("%s\n",p->name);  p での作業 (ノード内容表示)
treewalk(p->right);
 p の右の子を起点として再帰呼出
}
}
28
2分探索木のトラバーサル (深さ優先)
 ノード内容表示の順序次第で，表示順序が変わる
 行きがけ順
void treewalk(struct tnode *p)
{
if (p!=NULL){
printf("%s\n",p->name);
treewalk(p->left);
treewalk(p->right);
}
}
p： NULL
p
Machilda
p
p
Emy
p
Rolla
p
Candy
画面表示
Lisa
Machilda
Emy
Candy
Lisa
Rolla
29
2分探索木のトラバーサル (深さ優先)
 ノード内容表示の順序次第で，表示順序が変わる
 通りがけ順
void treewalk(struct tnode *p)
{
if (p!=NULL){
treewalk(p->left);
printf("%s\n",p->name);
treewalk(p->right);
}
}
p： NULL
p
Machilda
p
p
Emy
p
Rolla
p
Candy
画面表示
アルファベット順 
Lisa
Candy
Emy
Lisa
Machilda
Rolla
30
レベルごとのトラバーサル (試験範囲外)
 木のレベル (深さ) ごとに，さらに同一レベルでは左から
右にノードをトラバーサルするには？
 配列 (TODOリスト) で実現配列 q： G
BH
A
D
CF
E
copy
BH
D
CF
E
配列 w： G
レベル終了時に配列 w が空なら終了
A
レベル 1
B
C
E
D
G
レベル 2
F
H
※ 教科書でこの配列を「スタック」と呼んでいるのは間違い
レベル 3
レベル 4
31
ヒープ
 ヒープ (heap：山，堆積) とは，すべての親が必ず2つの
子を持つ (最後の要素は左の子だけでも良い) 完全2分木で，
どの親と子をとっても，親≦子になっている木を言う．
1
2
4
配列表現：
10
ノードを深さごとに
左から順に配列に格
納する
3
25
15
5
30
6
26
7
20
29
※ ヒープにおいては添え字は
0 でなく 1 から始める．
35
40
27
28
22
こうすると，子 s の親 p は，
p=s/2 で求まる．
1
2
3
4
5
6
7
8
9
10 11 12
10 25 15 30 26 20 29 35 40 27 28 22
例）11/2=5 (整数演算)
8
p.303-307
9 10
11
12
32
ヒープへのデータ追加 (上方移動)








既に存在するヒープへ新規データを追加することを考える．
その手順は以下の通りである：
(1) 新しいデータをヒープの最後の要素として格納する．
(2) その要素を子とする親のデータと比較し，親の方が大
きければ子と親を交換する．
(3) 次に，その親を子とする親 (おじいちゃん) との間で
比較を行い，必要があれば交換．これを，子の位置が根ま
で上がるか，親≦子になるまで繰り返す．
教科書 p.304 の図6.13を参照せよ．
この手順を上方移動 (shift up) という．
ソースコードは p.305.
33
ヒープへのデータ追加 (上方移動)
 (1) 新しいデータをヒープの最後の要素として格納する．
 (2) その要素を子とする親のデータと比較し，親の方が大きければ子と親
を交換する．
 (3) 次に，その親を子とする親 (おじいちゃん) との間で比較を行い，必
要があれば交換．これを，子の位置が根まで上がるか，親≦子になる
まで繰り返す．
1
10
25
12
4
30
12
25
35
9
30
12
15
5
26
8
3
2
6
20
7
29
s= 2
4
9
p= 1
4
2
34
ヒープの作成 (下方移動)
 上方移動では既存のヒープにデータを一つずつ追加することに
よりヒープを作成したが，既存の全データをそのまま2分木に
割り当ててから，ヒープとして整えるという方法がある．その
手順は以下の通り (教科書は分かりにくい)：
(1) 子を持つ最後の親 (データ数が n のとき，n/2) i から開始し，
全ての親に対して逆順に (n/2, n/2-1, n/2-2, …, 1)，以下の
(2)～(4) の手順を繰り返す．
(2) 親の番号を p とし，２つの子 (2p, 2p+1) のうちで小さい方を s
とする．(一番最後の親は，左側にしか子を持たない場合がある．
この場合は自動的に s = 2p とする.)
(3) 子 s の値が，親 p 以上なら，(1) のループで次へ．
(4) p と s の値を交換し，交換された子の方を親として (p = s， s
= 2p)，(2) へ戻る．
35
ヒープの作成 (下方移動)
 図的に理解しよう．  (1) 子を持つ最後の親から開始してループ
(最初は 9/2 = 4 から)
 (2) 親の番号を p とし，2p と 2p+1 で小
さい方の子を s とする．
 (3) s が p より大きいときは (1) ループで
次へ．
1
2
3
i= 4
p= 6
2
7
4
8
1
3
s= 12
7
14
4
8
16
6
3
7
1
2
4
2
4
3
2
3
4
8
4
9
1
 (4) p と s を交換し，p=s, s=2p とする．
1
7
6
8
2
5
9
5
7
6
6
s>n なら (1) ループで次へ．
s<=n なら (2) へ．
3
8
1
7
(2) から (4) の手順を
下方移動 (shift down)
と呼ぶ
ソースコード：p.307
36
ヒープ・ソート
 ヒープを用いたソーティングアルゴリズムがヒープ・ソー
トである．手順は大まかに以下の通り：
(1)与えられた数列からヒープを作成する．
(2)根ノードには最小値が来ているはずなので, これを取り外
す．その代わり，最後のノード (データ数 n なら n番の要
素) を切り離して根ノードに持ってくる．
(3)これにより残ったデータ (n-1個) のヒープ条件が狂った
ので，下方移動を使ってヒープの修正を行う. この場合，
根ノードからの1回の下方移動を行うだけでよい．
(4)(2) に戻る．
 教科書 p.308 の図6.15 を参照せよ．
p.308-311
37
ヒープ・ソート (ソースコード)
 p.309．
 関数 swap() は2つの配列要素の交換．
 main関数内，最初の whileループは初期ヒープの作成．
データを入れるごとに，入れたデータを最後尾に格納した
上で，上方移動を使ってヒープを整える作業を繰り返して
いる．
 2つめの whileループは，データを取り出すごとのループ．
 最初にルート (1番) と最後尾 (n番) を交換して，最後尾
をヒープから除外している (n--)．
 次のループは，視点 p を根に初期化して下方移動を1回
行っている部分．
 p.311 では，初期ヒープ作成を下方移動で行っている．
38
第7章：グラフ
 リスト構造は，ノード群を鎖状につないだもので，分岐は
なかった．一方木構造は分岐はするが，分岐した枝同士は
分かれたまま．
 これらをより一般化したものがグラフ (graph) である．
グラフでは，ノード間の連結は任意であり，ループを含む
こともある．
6
2
5
4
1
8
7
3
p.331-333
39
グラフとは
 円で描いた部分はノード (node 節点，vertex 頂点ともい
う) であり，それを結んでいるのはエッジ (edge 辺，
branch 枝) である．ノード1と2はつながっているが，1
と3はつながっていない．
エッジ
ノード
6
2
5
4
1
8
7
3
40
グラフとは
 グラフをデータとして表現するときに使われるのは隣接行
列 (adjacency matrix) である．ノード i と j の間に接続
がある場合は 1，ない場合は 0 としておく．
2
4
1
3
5
6
教科書ではノード番号は1からとしている．
j
8
7
対角成分は，同じノードへの接続をあると
するかどうかに関係する (この場合はなし
としている)．
1 2 3
4 5 6 7
8
1
0
1
0
0
0
0
0
0
2
1
0
1
1
0
0
0
0
3
i 4
5
0
1
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
1
0
0
6
0
0
0
0
1
0
1
1
7
8
0
0
1
0
0
1
0
1
0
0
0
0
0
1
1
0
41
グラフとは
 ここまでの例では，グラフのエッジには向きはなかった．
このようなものを無向グラフ (undirected graph) という．
 これに対して,「進める方向」のような向きを含んだグラ
フを有向グラフ (directed graph) という．この場合，隣
接行列は，ノード i から j へのエッジに対して，要素 (i,
j) は 1，要素 (j, i) は 0 としておく (p.333 図7.4)．
6
2
5
4
1
8
7
3
42
深さ優先探索
 グラフのノードにデータが記載されている場合，この中か
ら特定のデータを探すとき，グラフの全てのノードを巡る
というアルゴリズムが必要となる．
 その一つは深さ優先探索 (depth first search, 縦型探索
とも呼ばれる) である．
(1)始点を出発し，ノード番号の若い順に進む位置を調べ，い
けるところ (エッジで連結されていてまだ訪問していない
ノード) まで進む．
(2)行き場所がなくなったら，まだいける方向の残っている分
岐点まで戻り，再びいけるところまで進む．
(3)行き場所が全てなくなったら終了 (来た道を戻る)．
p.334-338
43
深さ優先探索
 どのように探索が進むかを図で見てみよう．
(1) 始点を出発し，ノード番号の若い順に進む位置を調べ，いけるところ
(エッジで連結されていてまだ訪問していないノード) まで進む．
(2) 行き場所がなくなったら，まだいける方向の残っている分岐点まで戻
り，再びいけるところまで進む．
(3) 行き場所が全てなくなったら終了 (来た道を戻る)．
2
4
1
3
5
6
8
7
44
深さ優先探索の再帰的解法
 深さ優先探索を再帰
的に行う関数は右の
通り．
 未探索の行き先を順
番に探して，行ける
ときは再帰呼び出し
でそこに進む．
 visit(1)を呼ぶと…
void visit(int i)
{
int j;
}
v[i]=1;
for (j=1;j<=N;j++){
if (a[i][j]==1 && v[j]==0){
printf("%d->%d ",i,j);
visit(j);
}
}
2
1
j= 2
4
j= 3
5
j= 4
6
j= 8
5
8
3
7
j= 7
j= 6
45
深さ優先探索 (ソースコード)
 2次元配列 a[][] によって隣接行列を記述 (初期化)．これ
がグラフの実体である．
 配列 v[N+1] は「訪問済みフラグ」を意味する．これが 0
となっているノードは未訪問，1 なら訪問済み．
 main関数では訪問フラグの初期化の後，visit(1) を呼び
出しているだけ．
 関数 visit() は再帰的関数であり，引数 i は探索を開始
するノードの番号．要するに「ノード i から先を探索せ
よ」という関数．
 visit() では，まず起点ノード i の訪問済みフラグを立て
る (1にする)．次に他の全てのノード j を調べ，ノード i
とつながっており (a[i][j]==1)，未訪問 (v[j]==0) な
らば, ノード j を起点として探索 (再帰呼出 visit(j))．
46
深さ優先探索の応用
 グラフ上の各ノードを起点として深さ優先探索を繰り返す
場合は，各探索の前に訪問済みフラグを下ろして置かなく
てはならない．
 p.337 図7.6 のように，ノード群が分かれているグラフを
非連結グラフと呼ぶ．これがどのように分かれているかを
調べるには，訪問済みフラグのリセットをせずに，各ノー
ドを起点とする探索を繰り返せばよい．
 探索の起点となるノードが訪問済みの場合は次のノードへ
進む．訪問済みでないときは，カウントを1つ進める．
 これにより，カウント数＝分かれている集団の数となる．
47
幅優先探索
 幅優先探索 (breadth first search，横型探索とも言う) で
は，「これから進まなくてはならないノードのメモ」を
キューの中に保存し，それを参照しながら探索を進める．
(1)始点をキューに入れる．
(2)キューからノードを取り出し，そのノードに連結している
未訪問のノードを全てキューに入れておく．
(3)キューが空なら終了，そうでないときは (2) へ．
 これにより，始点から近いノードから順序よく探索が進め
られる．
p.339-342
48
幅優先探索
(1)始点をキューに入れる．
(2)キューからノードを取り出し, 訪問済みとする. そのノー
ドに連結している未訪問ノードを全てキューに入れておく．
(3)キューが空なら終了，そうでないときは (2) へ．
ソースコード：p.340-341
6
2
5
4
1
8
7
3
キュー：
1
2
3
4
5
7
6
8
49
トポロジカル・ソート
 グラフを見ると，2から仕事を始めたとき，4や7ができる
ためには，1, 3 が出来ていなければならないのと同時
に，右側では 5, 6, 8 が出来ていなければならない．
教科書に誤植
 つまり，2, 1, 3, 4, 7 という系列と 2, 5, 4, 6, 8, 7 とい
う系列がある．従って，2の次に行いうる仕事，1と5では
どちらを先に行っても良い．このように必ずしも順序を比
較できない場合がある順序関係を半順序関係 (partial
order) という．
6
2
5
1
3
p.343-345
8
4
7
50
トポロジカル・ソート
 半順序関係が与えられたデータに対して，最初に行う仕事
から最後に行う仕事を1列に並べることをトポロジカル・
ソート (topological sort) という．
 どちらを先にやっても良い部分が含まれているので，解は
1つとは限らず，どれかが得られればよい．
2
5
6
8
4
1
3
7
51
トポロジカル・ソート
 有向グラフに対する深さ優先探索を繰り返し実行し，行き
着いたところから来た道を戻ろうとするときに，そのノー
ドを記録していけばよい．
 記録は「最後に行き着く場所」から順に行われるので逆
順．
2
6
5
8
4
1
7
3
2
5
6
8
1
3
7
4
52
Euler の一筆書き
 辺を消しながら深さ優先探索を行い，出発点に戻った
時に全ての経路が消えていれば，そのとき通った経路
が求める経路である
スタック v[n]
1
1
2
3
p.348-350
4
1
2
4
3
2
1
4
ソースコード：p.350
ネットワーク
 各辺に重みが定義されているグラフを重み付きグラフ
あるいはネットワーク (network) と呼ぶ．
 重みの意味は，例えば道路網については道路の長さであっ
たり，水道網なら流量だったりである (p.359 図7.22)．
1 2 3 4 5 6 7 8
 データの実体は，重み行列で
1 0 1 7 2 M M M M
記述する．
e
2
b
1
7
a
1
4
f
2
6
d
2
3
c
5
2
g
h
2
1
0
M
M
2
4
M
M
3
7
M
0
M
M
2
3
M
4
2
M
M
0
M
M
5
M
5
M
2
M
M
0
1
M
M
6
M
4
2
M
1
0
M
6
7
M
M
3
5
M
M
0
2
8
M
M
M
M
M
6
2
0
(M：無限大)
54
最短路問題 (Dijkstra のアルゴリズム)
解きたい問題：ノード a から h までの最短距離を求める
全てのノードの確定フラグを下ろし, 距離値を無限大で初期化
スタートノードの距離値を 0 とする．(3), (4) を N 回繰り返す
距離値最小の未確定ノードの番号を p とし，確定フラグを立てる
p につながる全ノードについて，p から進んだときの距離値が現在の
距離値より小さくなるとき，そのノードの距離値を更新する
 あるノードの距離値を更新するとき，
M
3
距離値だけでなく「この距離値に
M 2
1
e
なる場合，直前のノードはこれ」と
1
b
4
いう「手前ノード情報」も記録する
M
5
4
1
f
 距離だけでなく経路も求まる
2

(1)
(2)
(3)
(4)
a
M 7
0
2
c
p.353-359
6
d 7
M
6
M
2
3
5
2
g
10
M
9
h
M
7
55
最短路問題の例
 障害物環境下での移動ロボットのナビゲーション
 コンフィギュレーション障害物の頂点をサブゴールとし，
可視グラフ (visibility graph) を構築，最短路を探索
sub-goal
obstacle
start
移動ロボットのナビゲーション
を主にやってるとこ：城間研
obstacle
goal
configuration obstacle
56
講義のおわりに
 本講義では，知能システム工学科の趣旨に則って，メカと
情報の融合分野を扱う上でのアルゴリズム・データ構造を
実践的に (ソース・コードをベースとして) 解説した．
 情報工学科における同名の講義とは異なり，理論的な議論
はほとんど行っておらず，情報に興味のある学生にとって
は不十分である．
 一方，組み込みシステムなど，ハードウェアに近いプログ
ラミングでは，マイコンや電子回路など，多くのハード
ウェアに関する知識が必要となる．
 それらについては，各自が必要に応じてより深く勉強する
こと．本講義は基礎の基礎しか扱っていない．
 講義終了後もアルゴリズム・データ構造に関する質問は随
時受け付ける．
57

Download Report