

グラフ構造、たとえばツリー構造を探索することを考えます。  
ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。

この時、

  * 幅優先探索はしばしばキューを用いて
  * 深さ優先探索はしばしばスタックを用いて

それぞれ実装されます。

これはちょうど、

  1. 各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で `push()` を行う
  2. 次のノードを `pop()` により取り出して、訪問する

という形で、これに使うデータ構造の部分だけを変えれば、共通のコードにまとめることができます。  
そのため実は似た2つの探索手段であることがわかり、  
また逆に本質的な差を、データ構造の側に見て取ることが出来るということだと思います。

こういった視点で、一般のグラフ構造における探索の順序において  
ノードに対する、ある来訪順序に対応した、それぞれのデータ構造や、  
その時の探索アルゴリズムの一般形と言ったものを知りませんか？

またこういった探索とデータ構造の関係性に、何か理論や法則を知りませんか？


CC BY-SA 4.0
2018-11-06T17:32:29.253
50024
2018-11-06T22:42:05.720
2018-11-06T22:42:05.720
30827
30827
question
アルゴリズム グラフ理論 データ構造
グラフ構造の探索に対応するデータ構造には法則があるのでしょうか？