アルゴリズムクイックリファレンス 第2版

154

■

6

章 グラフアルゴリズム

びその重さ）を返すイテレータを構築して利用できる。

更新（Update）

グラフに辺を追加（あるいは削除）できる。グラフに節点を追加（あるい

は削除）もできるが、本章のアルゴリズムは節点の追加削除を必要としな

い。

グラフを探索する方法についての議論から始める。一般的な

2

つの探索戦略は、

深さ優先探索

と

幅優先探索

である。

6.2

 深さ優先探索

図6-5の左の迷路を考えよう。何度か練習すれば、子供でも始点

s

から目的

t

への

経路をすぐに見つけられるようになる。この問題を解く

1

つの考え方は、とりあえ

ず進めるだけ進めば、目的地からそう離れてはいないところにいるだろう、という

考え方だ。すなわち、分岐でランダムに方向を選んでは、その方向へ進むことを繰

り返す、という方法だ。どこから来たかをマークしておき、行き止まりに達するか、

既に来たことのあるところに行くしかない状態に陥ったら、後戻りしてこれまで試

したことのない経路があ

る分岐を探し、そこから再開する。図6-5の右側につけた

番号は、この方法で解いた際の分岐点を示す。この例の場合には、迷路のすべての

場所が訪問されている。

図6-5　s から tへの小さい迷路

図6-5の迷路をグラフで表現することができる。節点は、迷路の分岐点（各節点に

は図6-5の右側の番号を付けた）と「行き止まり」とで作られる。辺は、節点の間に、

迷路での分岐のない直接の道があるときだけ作られる。図6-5の迷路の無向グラフ

6.2

 深さ優先探索

■

155