【TypeScriptで学ぶアルゴリズム】深さ優先探索(DFS)

深さ優先探索

木構造のデータを調べていく際に左側（片方）のノードを進めるだけ巡回し、先端まで辿り着いたら親要素へ戻り右側の要素へ進んでいくといった処理を繰り返す探索方法です

深さ優先探索の実装例

1. グラフを表すデータの型定義

dfs.ts

//グラフの隣接リストを表す型
type Graph = { [key: string]: string[] };

2. DFSの実装

dfs.ts

function dfs(graph: Graph, start: string, visited: Set<string> = new Set()): void {
  //開始ノードを巡回済みとしてセットに追加
  visited.add(start);
  console.log(start); //巡回したノードを表示

  //隣接するすべてのノードに対して探索を実行
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited); //再帰的にDFSを実行する
    }
  }
}

グラフデータの定義

dfs.ts

const graph: Graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
};

実行！

dfs.ts

//'A'ノードからDFSを開始します
dfs(graph, 'A');

出力結果

A
B
D
E
F
C

上記を見るとしっかり深さ優先探索されていることが分かります！
（ノードAからスタートし、B -> D -> E -> F -> Cという順序で巡回します）