DFS(Depth-First Search)

グラフィック変換(グラフィック順序)

(1)定義:深度優先ナビゲーション

-1つのパスで最後に移動し、到着しない場合は次のパスに移動します.

(2)特徴

-循環アルゴリズム形式を持つ.
-ノードにアクセスしたかどうかを確認する必要があります.

(3)プロセス

1.aノード(開始ノード)にアクセスします.
アクセスしたノードは、アクセスしたことを示します.
2.aに隣接するノードを順次巡回する.
aに隣接するノードがない場合、終了します.
aに隣接するノードbにアクセスした場合、aに隣接する他のノードにアクセスする前に、bのすべての隣接ノードにアクセスしなければならない.
bを起点としてDFSを再起動し、bの隣接ノードにアクセスする.
4.bの分岐はすべて完璧に探索された場合,隣接するaの頂点の中でまだアクセスされていない頂点を探す.
すなわち,bのブランチを完全に探索した後にのみ,aの他の隣接ノードにアクセスできる.
まだ頂点にアクセスしていない場合は、終了します.
ある場合は、頂点を始点としてDFSを再起動します.

（4）時間複雑度

-図面を隣接行列として表示します.
for loopはVのように回転するので、O(V)時間がかかり、頂点に戻るたびにDFSが呼び出されるので、O(V^2)
(V:幹線セット)
-図面を隣接リストとして表示します.
DFS全体が終了した後、DFSの終了時に各頂点に1回アクセスし、各幹線を1回チェックすることを考慮できます.O(V+E)です.
(V:幹線セット,E:ノードセット)

（5）実施

  // DFS
  traverseDFS(vertex) {
    const visited = {};
    this._traverseDFS(vertex, visited);
  }
  _traverseDFS(vertex, visited) {
    visited[vertex] = true;
    console.log(`방문한 노드 : ${vertex}`);
    for (let adjacentVertex in this.edges[vertex]) {
      if (!visited[adjacentVertex]) {
        this._traverseDFS(adjacentVertex, visited);
      }
    }
  }