オープンリスト/クローズドリスト
オープンリストとクローズドリストは、深さ優先探索(depth-first search, DFS)と幅優先探索(breadth first search, BFS)を実装するうえでなくてはならない概念である。
オープンリスト - 発見はしている対象を格納するリスト
クローズドリスト - 発見も探索も終わっている対象を格納するリスト
深さ優先探索
図1
図1のようなデータ構造なり、なんなりがあったとする。この時、Fを発見したい対象と仮定する。DFSだろうとBFSだろうが最初にAへ向かう。ここではDFSだけのオープンリストとクローズドリストを表示する。DFSではリストはスタックとして実装される。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
となる。次にAを探索するので表は以下のようになる。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| B D | A |
さらに次にBを探索するので
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| B D | A |
| C E D | A B |
さらに、次はCを探索する。ここで重要なのは、オープンリストはスタックとして実装される。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| B D | A |
| C E D | A B |
| E D | A B C |
次は、スタックなのでEDのEを先に探索する。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| B D | A |
| C E D | A B |
| E D | A B C |
| D | A B C E |
最後にスタックに残っているのはDなのでDを探索するとFを発見する。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| B D | A |
| C E D | A B |
| E D | A B C |
| D | A B C E |
| F | A B C E D |
最後に目的のFを探索して終了である。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| B D | A |
| C E D | A B |
| E D | A B C |
| D | A B C E |
| F | A B C E D |
| 空 | A B C E D F |
時間計算量:
DFSでは各ノードを1回ずつ訪れ、各エッジも1回ずつ走査する。
ノード数をN、エッジ数をEとすると、時間計算量は O(N + E) となる。
二分木の場合、エッジ数は常にノード数より1少ない（E = N - 1）。
したがって、この場合の時間計算量は O(N) となる。
具体的には:
ノード数: 6 (A, B, C, D, E, F)
エッジ数: 5 (A-B, A-D, B-C, B-E, D-F)
時間計算量: O(6) = O(N)
空間計算量:
DFSの空間計算量は主に再帰呼び出しのスタックによって決まる。
最悪の場合、スタックの深さは木の高さに等しくなる。
完全二分木の場合、高さは約 log₂N だが、この木は完全ではない。
この特定の木の高さは3である。
したがって、この木に対するDFSの空間計算量は O(h) となる。ここで h は木の高さである。
具体的には O(3) だが、一般的には O(h) と表現する。
まとめ:
時間計算量: O(N) ここで N はノード数
空間計算量: O(h) ここで h は木の高さ
この例では N=6, h=3 だが、一般的な二分木に対してこれらの計算量が適用される。
幅優先探索
同様の木に対して行う。このときBFDのリストではキューが適応される。
まずAを発見する。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
次に、Aを探索してBDを発見する。BDの順で発見するとして、この時のオープンリストはキューなのでBが先に入る。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| D B | A |
次に、Bを探索するとCEを発見する。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| D B | A |
| E C D | A B |
先ほどは、そのままB側の木を探索していたが、キューなのでD側に移る。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| D B | A |
| E C D | A B |
| F E C | A B D |
ここまでくるとわかると思うので、この先は結果のみを表示する。
| オープンリスト | クローズドリスト |
|---|---|
| A | 空 |
| D B | A |
| E C D | A B |
| F E C | A B D |
| F E | A B D C |
| F | A B D C E |
| 空 | A B D C E F |
これで、幅優先探索は終了である。
時間計算量:
BFSもDFSと同様に、各ノードを1回ずつ訪れ、各エッジも1回ずつ走査する。
ノード数をN、エッジ数をEとすると、時間計算量は O(N + E) となる。
二分木の場合、エッジ数は常にノード数より1少ない（E = N - 1）。
したがって、この場合の時間計算量は O(N) となる。
具体的には:
ノード数: 6 (A, B, C, D, E, F)
エッジ数: 5 (A-B, A-D, B-C, B-E, D-F)
時間計算量: O(6) = O(N)
空間計算量:
BFSの空間計算量は主にキューのサイズによって決まる。
最悪の場合、キューのサイズは木の最大幅（最も要素数の多い階層のノード数）に等しくなる。
この特定の木の最大幅は2である（BとDの階層）。
一般的な二分木では、最大幅は木の最下層に現れ、最大でN/2となる可能性がある。
したがって、この木に対するBFSの空間計算量は O(w) となる。ここで w は木の最大幅である。
具体的には O(2) だが、一般的な二分木では O(N) となる可能性がある。
まとめ:
時間計算量: O(N) ここで N はノード数
空間計算量: O(w) ここで w は木の最大幅（この例では2、一般的には最大 N/2）
この例では N=6, w=2 だが、より大きな二分木では空間計算量が O(N) に近づく可能性がある点に注意が必要である。BFSの空間計算量は、一般的にDFSよりも大きくなる傾向がある。特に、幅の広い木や完全二分木に近い形状の場合、その差が顕著になる。
まとめ
深さ優先探索はスタックを使って、幅優先探索はキューを使う。
たぶん、これぐらいは皆さん知ってると思うけど、別々の授業で散々出てきたので、書いときます。