Loading article…
コンピュータサイエンスにおいて、グラフ走査（グラフ探索とも呼ばれる）とは、グラフ内の各頂点を訪問（確認および／または更新）するプロセスを指します。このような走査は、頂点を訪問する順序によって分類されます。木構造の走査は、グラフ走査の特殊なケースです。
木構造の走査とは異なり、グラフの走査では、ある頂点に遷移する前にその頂点が既に探索済みであるかどうかが必ずしも分からないため、一部の頂点を複数回訪問する必要が生じる場合があります。グラフが密になるにつれて、この冗長性が顕著になり、計算時間が増加します。一方、グラフが疎になるにつれて、計算時間は短縮されます。
したがって、アルゴリズムが既に探索した頂点を記憶しておくことが通常必要となります。これは、頂点の再訪問をできるだけ少なくするため（あるいは最悪の場合、探索が無限に続くのを防ぐため）です。これは、探索中にグラフの各頂点に「色」または「訪問」状態を関連付け、アルゴリズムが各頂点を訪問するたびにその状態をチェックして更新することで実現できます。頂点が既に訪問されている場合は、その頂点は無視され、それ以上パスは進みません。そうでない場合は、アルゴリズムは頂点をチェック/更新し、現在のパスを進み続けます。
グラフのいくつかの特殊なケースでは、構造内の他の頂点の訪問が暗黙的に含まれており、そのため、走査中に訪問を明示的に記録する必要はありません。その重要な例が木です。木では、走査中に、現在の頂点のすべての「祖先」頂点（およびアルゴリズムによってはその他の頂点）が既に訪問されていると想定できます。深さ優先探索と幅優先探索はどちらも木ベースのアルゴリズムの応用であり、主に構造的に決定された「ルート」頂点がないことと、走査の訪問状態を記録するためのデータ構造が追加されている点で区別されます。
注記：グラフの各頂点を木構造に基づくアルゴリズム（深さ優先探索や幅優先探索など）で走査する場合、グラフの各連結成分に対して少なくとも1回はアルゴリズムを呼び出す必要があります。これは、グラフのすべての頂点を順に走査し、未訪問の頂点ごとにアルゴリズムを実行することで容易に実現できます。
深さ優先探索（DFS）は、有限グラフを走査するためのアルゴリズムです。DFSは、兄弟頂点を訪れる前に子頂点を訪れます。つまり、特定のパスの幅を探索する前に、その深さを走査します。このアルゴリズムを実装する際には、一般的にスタック（多くの場合、再帰によるプログラムのコールスタック）が使用されます。
このアルゴリズムは、まず選択された「ルート」頂点から開始します。次に、現在の頂点から隣接する未訪問の頂点へと繰り返し遷移し、現在の位置から遷移できる未探索の頂点が見つからなくなるまで続けます。その後、アルゴリズムは以前に訪れた頂点に沿って逆戻りし、さらに未探索の領域につながる頂点が見つかるまで進みます。そして、以前と同様に新しい経路を進み、行き止まりに遭遇した場合は逆戻りし、最初のステップで設定した元の「ルート」頂点を過ぎて逆戻りした時点で終了します。
DFSは、トポロジカルソートや平面性テストなど、多くのグラフ関連アルゴリズムの基礎となっている。
手順DFS( G , v )は、 Gのすべてのエッジeに対して、v を探索済みとして ラベル付けします。エッジeが未探索の場合、w ← G .adjacentVertex( v , e )頂点wが未探索の場合、eを 発見済みエッジとして ラベル付けします。 再帰的に DFS( G , w ) を呼び出す。そうでない場合は、 e をバックエッジとして ラベル付けする。
幅優先探索（BFS）は、有限グラフを走査するもう一つの手法です。BFSでは、子頂点を訪れる前に兄弟頂点を訪れ、探索プロセスではキューが使用されます。このアルゴリズムは、ある頂点から別の頂点への最短経路を見つけるためによく用いられます。
手順BFS( G , v )は、 キューQを作成し、 v をQに 追加し、 v をマークします。Qが空でない間、 w ← Q .dequeue() を実行します。wが探しているものであれば、w を 返します。G .adjacentEdges( w )内のすべてのエッジeに対して、x ← G .adjacentVertex( w , e ) を実行します。xがマークされていない場合は、xを マークし、 xをQに 追加します。null を返します。
幅優先探索は、グラフ理論における多くの問題を解決するために使用できます。例えば、次のようになります。
グラフ探索問題は、グラフ走査の変形と見なすことができます。これはオンライン問題であり、グラフに関する情報はアルゴリズムの実行中にのみ明らかになります。一般的なモデルは次のとおりです。非負のエッジ重みを持つ連結グラフG = ( V , E )が与えられます。アルゴリズムは、ある頂点から開始し、すべての接続する出力エッジと、それらのエッジの終点となる頂点を知っていますが、それ以上の情報は知りません。新しい頂点を訪れると、再びすべての接続する出力エッジと終点となる頂点がわかります。目標は、すべてのn個の頂点を訪れて開始頂点に戻ることですが、巡回経路の重みの合計はできるだけ小さくする必要があります。この問題は、巡回セールスマンが移動しながらグラフを発見しなければならない、巡回セールスマン問題の特定のバージョンとして理解することもできます。
一般的なグラフの場合、無向グラフと有向グラフの両方で最もよく知られているアルゴリズムは、単純な貪欲アルゴリズムです。
普遍的走査シーケンスは、任意の頂点数を持つ正則グラフと任意の開始頂点に対するグラフ走査を構成する命令のシーケンスです。確率的証明は、Aleliunas らによって、 n 個の頂点を持つ任意の正則グラフに対して、命令数がO ( n 5 )に比例する普遍的走査シーケンスが存在することを示しました。[ 6 ]シーケンスで指定されるステップは、絶対ではなく、現在のノードに対する相対的なものです。たとえば、現在のノードがv jで、v jにd 個の隣接ノードがある場合、走査シーケンスは、次に訪問するノードv j +1をv jのi番目の隣接ノードとして指定します。ここで、1 ≤ i ≤ dです。