このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

グラフ探索アルゴリズム

 グラフの最も基本的アアルゴリズムは、すべての節点や枝を通って処理を行うことである。このとき2回以上同じ節点や枝を通らないようにしながら、1回は必ず通るように、系統だった手順が必要になる。このように系統立ててグラフを調べることをグラフの探索という。

グラフ探索アルゴリズムの種類

 グラフの探索アルゴリズムの代表的なものとして、深さ優先探索と幅優先探索がある。

深さ優先探索

 グラフを深いほうへと進み、行き止まったら後戻りしてまた深いほうへ進みながら頂点を探索していく方法である。2分木の頂点を深さ優先で訪れる順番は次のようになる。

 この「親→左の子→右の子」の順の先行順(ABDECFG)の他に、「左の子→親→右の子」の順の中間順(DBEAFCG)、「左の子→右の子→親」の順の後行順(DEBFGCA)も存在する。

 深さ優先探索では、ある頂点を訪れたとき、その頂点と辺で繋がっている頂点をスタックに入れておく。そして、スタックから頂点をひとつ取り出して(POP)、その頂点を訪れ、その頂点と辺で繋がっている頂点をスタックに入れる(PUSH)。これを繰り返す(同じ頂点は何度も訪れない)。スタックなのでLIFOの仕組みである。

幅優先探索

 ある階層をすべて調べ、それが終わるとひとつ深い階層をすべて調べるということを繰り返す。幅優先探索では、頂点Bの次に頂点Cへ行くところが特徴である。

 幅優先探索では、ある頂点を訪れたとき、その頂点と辺で繋がっている頂点をキューに入れておき(ENQUEUE)、キューから頂点をひとつ取り出して(DEQUEUE)、その頂点を訪れ、その頂点と辺で繋がっている頂点をキューに入れる。これを繰り返す(同じ頂点は何度も訪れない)。キューなのでFIFOの仕組みである。

例:次のグラフを幅優先探索してみる。

1:,叛椶靴討い訐疆世鮹気掘▲ューに入れる(キュー:↓ぁ法Kれた節点にも,鯑れる(訪問済み: 法

2:キューの最初の節点(◆砲鬚劼箸勅茲蟒个掘∨れた節点に入れて(訪問済み:、◆法△修寮疆澄吻ぁ砲叛椶靴討い訐疆世鮹気掘▲ューに入れる。ただし、訪問済みの節点( 砲禄く(キュー:きァ法

3:後は、ステップ2をキューが空になるまで続ける。結果として、探索は「、□あ→アБΒ│」となる。

参考文献

  • 『ソフトウェア開発技術者 合格エッセンシャルハンドブック』
  • 『ソフトウェア開発技術者試験対策 コンピュータサイエンス補足資料+午後演習問題』