モダンJavaScript入門: 深さ優先探索(DFS)を使用したグラフ探索

1. 深さ優先探索(DFS)とは

深さ優先探索（DFS: Depth-First Search）は、グラフの探索アルゴリズムの一つで、根から深く（遠く）のノードを優先的に探索する方法です。スタックというデータ構造を用いて実装することが一般的です。

2. DFSのアルゴリズムとコード例

DFSの基本的なアルゴリズムは以下の通りです。

初期ノードをスタックに追加する。
スタックが空になるまで以下の操作を繰り返す。
1. スタックからノードを一つ取り出す（pop）。
2. そのノードが目的のノードなら探索を終了する。
3. そうでなければ、そのノードの隣接ノードのうち未探索のものを全てスタックに追加する。

JavaScriptによるDFSのコード例は以下の通りです。

class Graph {
  constructor(nodes) {
    this.nodes = nodes;
    this.adjList = new Map();
    nodes.forEach(node => this.adjList.set(node, []));
  }

  addEdge(node1, node2) {
    this.adjList.get(node1).push(node2);
    this.adjList.get(node2).push(node1);
  }

  dfs(node, visited = new Set()) {
    if (visited.has(node)) return;
    console.log(node);
    visited.add(node);
    this.adjList.get(node).forEach(neighbor => this.dfs(neighbor, visited));
  }
}

const g = new Graph(['A', 'B', 'C', 'D', 'E', 'F']);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('B', 'E');
g.addEdge('C', 'F');
g.dfs('A'); // or any node

3. DFSの応用例

DFSは様々な問題に応用できます。ここでは、迷路の解決、連結成分の検出、トポロジカルソートの3つを例に挙げます。

3.1 迷路の解決

DFSは迷路問題を解くのにも使われます。ここでは、迷路の入口から出口までの経路を見つける例を示します。

class MazeSolver {
  constructor(maze, start, end) {
    this.maze = maze;
    this.start = start;
    this.end = end;
  }

  getNeighbors([x, y]) {
    return [
      [x - 1, y],
      [x + 1, y],
      [x, y - 1],
      [x, y + 1]
    ].filter(
      ([x, y]) =>
        x >= 0 && x < this.maze.length && y >= 0 && y < this.maze[0].length
    );
  }

  dfs(start, visited = new Set()) {
    const key = `${start[0]},${start[1]}`;
    if (visited.has(key) || this.maze[start[0]][start[1]] === 1) return false;
    visited.add(key);

    if (start[0] === this.end[0] && start[1] === this.end[1]) return true;

    for (let neighbor of this.getNeighbors(start)) {
      if (this.dfs(neighbor, visited)) return true;
    }

    return false;
  }

  solve() {
    return this.dfs(this.start);
  }
}

const maze = [
  [0, 0, 0, 0, 0],
  [1, 1, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [1, 0, 1, 1, 1],
  [0, 0, 0, 0, 0]
];
const start = [0, 0];
const end = [4, 4];
const solver = new MazeSolver(maze, start, end);
console.log(solver.solve()); // true or false

3.2 連結成分の検出

グラフがいくつの連結成分に分かれているかを見つけるのにDFSを使うことができます。

class Graph {
  // ...省略...

  dfs(node, visited = new Set()) {
    if (visited.has(node)) return;
    visited.add(node);
    this.adjList.get(node).forEach(neighbor => this.dfs(neighbor, visited));
    return visited;
  }

  getConnectedComponents() {
    const visited = new Set();
    const components = [];
    this.nodes.forEach(node => {
      if (!visited.has(node)) {
        const component = this.dfs(node);
        components.push([...component]);
        component.forEach(node => visited.add(node));
      }
    });
    return components;
  }
}

const g = new Graph(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('B', 'E');
g.addEdge('C', 'F');
g.addEdge('G', 'H');
console.log(g.getConnectedComponents()); // [['A', 'B', 'C', 'D', 'E', 'F'], ['G', 'H']]

3.3 トポロジカルソート

有向非巡回グラフ（DAG）のノードを順序付けるトポロジカルソートにもDFSは使われます。

class Graph {
  // ...省略...

  topoSortUtil(node, visited, stack) {
    visited.add(node);
    this.adjList.get(node).forEach(neighbor => {
      if (!visited.has(neighbor)) this.topoSortUtil(neighbor, visited, stack);
    });
    stack.push(node);
  }

  topoSort() {
    const visited = new Set();
    const stack = [];
    this.nodes.forEach(node => {
      if (!visited.has(node)) this.topoSortUtil(node, visited, stack);
    });
    return stack.reverse();
  }
}

const g = new Graph(['A', 'B', 'C', 'D', 'E']);
g.addEdge('A', 'C');
g.addEdge('B', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'E');
console.log(g.topoSort()); // ['B', 'D', 'A', 'C', 'E']

以上、深さ優先探索(DFS)を使用したグラフ探索の基本的な理解と応用例について学びました。これからDFSを用いた様々な問題解決にチャレンジしてみてください。

AIko Code Symphony