アルゴリズム|深度優先ナビゲーションDFSアルゴリズム-グラフィックナビゲーション

深度優先(Depth Priority)(DFS)を使用してグラフィックを参照します.

グラフィックの参照

1つの頂点から順にすべての頂点に1回アクセスします.
ある都市から別の都市へ、電子回路に特定の端子と端子が接続されているかどうかを見ることができます.

深度優先ナビゲーションDFS

DFSは探索において深さを優先的に探索するアルゴリズムである.
幅優先ナビゲーション(BFS)はキュー(queue)を使用し、深さ優先ナビゲーション(DFS)はスタック(stack)を使用します.
実際,計算機はスタック原理呼び出し関数を用いるため,再帰を用いてDFSを実現できる.

のすべてのノードにアクセスする場合は、このメソッドを選択します.すべての状況の数はとてもきれいです!

速度は

BFSより遅い.

にアクセスしたノードを確認します.

DFSの動作方式

アクセスされていない隣接ノードがある場合、アクセスおよび処理が行われる.

アクセスされていない隣接ノードがない場合(すべてアクセスされている場合)、  ツアーを終了します.

グラフィックナビゲーションの例

白駿1260https://www.acmicpc.net/problem/1260
次の図がある場合は、DFSを使用してアクセスしてみます.

頂点には1～4番のノードがあります.

幹線は互いに以下のように接続されている.

ノード接続ノード12,3,421,431,441,2,3

出発ノードは1番ノードです.

次に、グラフのアクセス順序を示します. 

黄色は現在ブラウズされているノード、グレーはアクセスされているノード、白はアクセスされていないノードです.

(1)現在のナビゲーションノード=1

ノード1に移動し、アクセス処理を行う.
接続された2,3,4はすべてアクセスされていません.その中でまず2日から探索を開始する.(2)で行います.

(2)現在のナビゲーションノード=2

ノード2に移動し、アクセス処理を行う.
2に接続されている1番と4番のノードでは、1番のノードがアクセス済みで、ブラウズせずに4番をブラウズします.(3)で行います.

(3)現在のナビゲーションノード=4

ノード4に移動し、アクセス処理を行う.
4に接続された1,2,3番ノードでは,1,2番ノードが既にアクセスしており,ブラウズせずに3番をブラウズする.(4)で行います.

(4)現在のナビゲーションノード=3

ノード3に移動し、アクセス処理を行う.
3に接続されている1、4ノードが既にアクセスされているため、ブラウズを終了します.
JavaScriptコードを使用して、上記のアルゴリズムを記述します.
function DFSを参照すればよい.

function solution(n, m, v, road) {
    let graph = Array.from(Array(n + 1), () => Array());
    let ch = Array(n + 1).fill(0);
    let answer = [];

    // 연결된 노드 표시하기
    for (let i = 0; i < m; i++) {
      graph[road[i][0]].push(road[i][1]);
      graph[road[i][1]].push(road[i][0]);
    }
    // 연결된 노드를 오름차순으로 정렬하기
    for (let i = 1; i <= n; i++) {
      graph[i].sort((a, b) => a - b);
    }

    function DFS(L) {
      // 방문한 노드면 탈출
      if (ch[L] === 1) return;
      else {
        // 방문하지 않았다면 인접한 노드 방문하기
        ch[L] = 1;
        answer.push(L);
        for (let node of graph[L]) {
          DFS(node);
        }
      }
    }

    DFS(v);
    return answer;
  }
  console.log(
    solution(4, 5, 1, [
      [1, 2],
      [1, 3],
      [1, 4],
      [2, 4],
      [3, 4],
    ])
  ); // [ 1, 2, 4, 3 ]
  console.log(
    solution(5, 5, 3, [
      [5, 4],
      [5, 2],
      [1, 2],
      [3, 4],
      [3, 1],
    ])
  ); // [ 3, 1, 2, 5, 4 ]
  console.log(
    solution(1000, 1, 1000, [
      [999, 1000],
      [999, 1000],
    ])
  ); // [ 1000, 999 ]

コメントリンク
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://blog.naver.com/ndb796/221230945092