Zenn
🔎

グラフアルゴリズムの基礎を学ぶーBFSとDFS

2023/05/06に公開
algorithm
graph
bfs
dfs
tech

この記事は、グラフアルゴリズムシリーズの2番目の記事です。

  1. 概念と表現方法
  2. BFSとDFS→現在地
  3. UnionFind
  4. 最小全域木
  5. 単一始点最短経路問題
  6. 全点対最短経路問題（WIP）

メンタルモデル

今回はグラフのデータの探索方法について紹介します。探索方法は概ね2つに分けられます。

  • 幅優先探索（BFS: Breadth-First Search）、探索のレベルとの概念を用いて、ノードに隣接する全てのノードを優先的に探索するアルゴリズムです。


BFSメンタルモデル（出典）

  • 深さ優先探索（DFS: Depth-First Search）、幅優先と違い、ノードの隣接ノードのどれか1つを選択して、隣接ノードがなくなるまで繰り返して探索するアルゴリズムです。


DFSメンタルモデル（出典）

ここで理解のためにまずは二分木の探索から見てみましょう。

二分木の探索

二分木のDFS探索には、pre-order, in-order, post-orderの方法があります。それぞれ、ノードに入ったとき、ノードの左枝が終わって右枝に入る前、ノードの左枝と右枝が終わってノードから離れるとき、のタイミングと対応しています。N分木にはin-orderがないため（枝が2つ以上あるため）、汎用性で言えば、pre-orderとpost-orderが用いられます。

post-orderの方は、左枝を優先に探索し、次に右枝、最後はノード自身となるので、DFSの実例でもあります。DFSは空間効率が高いのですが、再帰の形でスタックに積んで行きます。テンプレート的な考え方をjsコードで表現すると以下となります。再帰についてあまり理解していないとここは苦しむかもしれませんが、原則として、現時点のノードにおいて何をするかだけを考えるのです。

// 二分木
class Node {
  constructor(val = 0, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}
function dfs(node) {
  if (node === null) return
  // preorder　この時点でまだ枝のトラバースが始まっていなく、node自身にある
  //-----
  dfs(node.left)
  //-----
  // inorder　この時点で左が終わったが右はまだ、今はnode自身にある
  //-----
  dfs(node.right)
  //-----
  // postorder　この時点で右と左の枝のトラバースが終わったため、その結果を持って何かの操作が可能
}

// N分木
class Node {
  constructor(val = 0, children = []) {
    this.val = val
    this.children = children
  }
}
function dfs(node) {
  if (node === null) return
  // preorder　この時点でまだ枝のトラバースが始まっていなく、node自身にある
  //-----
  for (const child of node.children) {
    dfs(child)
  }
  //-----
  // postorder　この時点で子供ノードのトラバースが終わったため、その結果を持って何かの操作が可能
}

DFSの深さ優先に対して、BFSの幅優先探索方法もありますが、再帰を利用しておらず、多少理解しやすいかもしれません。考え方としては、任意のノードにおいて、そのノードの子供ノードを一つのキューに入れて、キューが空になるまで処理を続けます。

function bfs(root) {
  let queue = [root] // 配列でキューを実装
  let depth = 0 // bfsが同じ階層のものを一度全部訪問するので、ここは階層を記録
  while (queue.length > 0) { // キューにノードがある限り処理を続ける
    const n = queue.length 
    // 現在のキューにあるノードに対してループ、ただもしdepthに関心がない場合これは不要
    for (let i = 0; i < n; i++) { 
      const node = queue.shift() // キューの先頭からノードを取り出す
      for (const child of node.children) { // ノードの隣接ノードをループ
        // ここで何か処理を行う、例えばターゲットノードであればリターン
        if (isTarget(child)) return child
        queue.push(child) // ノードをキューにプッシュ
      }
    }
    // ここで階層を1つ増やす
    depth++
  }
}

グラフまで拡張

木とグラフはどちらかというとかなり近いデータ構造になります。一番大きな区別というと、木にはサイクルが存在しないが、グラフにはサイクルが存在する（ことができる）ところです。

この違いにより、グラフを探索するときに一つ問題が生じます。訪問済みのノードに戻ってしまい、無限ループになる問題があるところです。この問題を解決するには、通常ハッシュセットを導入して、訪問済みのノードを記録することです。

木の知見をグラフに応用すると、右と左の枝とは限らず、一般的に任意のノードに対して、隣接ノードを配列の形で保存すると考えても良いかと。また、グラフにサイクルの存在があり得るため、訪問済みをマークするためにハッシュセットが必要。それ以外にほぼ同じように見えますね。

class Node {
  constructor(val = 0, neighbors = []) {
    this.val = val
    this.neighbors = neighbors
  }
}

// 再帰で書く
function dfs(root, visited) {
  if (!root) return
  for (const neighbor of root.neighbors) { // ノードの隣接ノードをループ
    if (visited.has(neighbor)) continue // 訪問済みの場合はスキップ
    visited.add(neighbor) // 訪問していない場合はハッシュセットに追加
    dfs(neighbor, visited) // ループ中のノードに対して再帰呼び出し
  }
}

// スタックで書く
function dfs(root) {
  const visited = new Set([root]) // ハッシュセットで訪問済みのノードを追加
  const stack = [root] // 配列でスタックを表現

  while (stack.length > 0) { // スタックにノードがある限り処理を続ける
    const currentNode = stack.pop() // ノードをスタックの上からとる

    for (const neighbor of currentNode.neighbors) { // ノードの隣接ノードをループ
      if (visited.has(neighbor)) continue // 訪問済みのノードはスキップ
      // この辺りで何か処理を行う
      stack.push(neighbor)
      visited.add(neighbor)
    }
  }
}

それでBFSの考え方も下記の通りで拡張すれば良いでしょう。

function bfs(root) {
  let queue = [root] // 配列でキューを表現
  let visited = new Set([root]) // ハッシュセットで訪問済みのノードを追加
  let depth = 0 // bfsが同じ階層のものを一度全部訪問するので、ここは階層を記録
  while (queue.length > 0) { // キューにノードがある限り処理を続ける
    const n = queue.length 
    // 現在のキューにあるノードに対してループ、ただもしdepthに関心がない場合これは不要
    for (let i = 0; i < n; i++) { 
      const currentNode = queue.shift() // キューの先頭からノードを取り出す
      for (const neighbor of currentNode.neighbors) { // ノードの隣接ノードをループ
        if (visited.has(neighbor)) continue // 訪問済みのノードはスキップ
        // この辺りで何か処理を行う
        queue.push(neighbor) // 訪問していないノードをキューにプッシュ
        visited.add(neighbor) // 同時に訪問済みとマーク
      }
    }
    // ここで階層を1つ増やす
    depth++;
  }
}

DFSとBFSの比較

一般的に言えば：

  • bfsは階層毎に進めるので、ノードの間の距離は常に最短、ただキューとかハッシュセットとかがあるためメモリ使用量がdfsより高い。
  • dfsは効率的に遠くにあるノードを見つけることができる、つまり深さと関わる問題に適している。最短も求められますが、全ての回答を見つけてその中からまた最短を絞り出すことになり、効率がbfsより良くない

つまり：

アルゴリズム 適している場面 良い点 悪い点
BFS (幅優先探索) 最短経路を見つける、全ノードを同じ階層で探索する 最短経路を見つけるのに適している、全ノードを均等に探索 空間効率が低い（キューに多くのノードを格納する必要がある）
DFS (深さ優先探索) グラフの全探索、循環を検出する、トポロジカルソートを求めるなど 空間効率が高い（スタックを使用）、探索が深く行われる 最短経路を見つけるのに適していない、探索が偏る場合がある

dfsはスタック＋再帰、bfsはキュー＋whileループというイメージです。表にまとめると：

項目 DFS BFS
トラバース順番 深さ・Depth 幅・Level
データ構造 スタック キュー
時間複雑度 O(V + E) O(V + E)
空間複雑度 O(V) O(V)
ルート特徴 狭いかつ長い 幅広いかつ短い

実践問題

ここでLeetcodeの1971. Find if Path Exists in Graphで例とします。

どの探索方法でもいけますが、要するに、ノードsrcからスタートして、ノードdstまで到達できるかどうかを判断すれば良いことです。

BFS方法

class Node {
  constructor(val, neighbors = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

class Graph {
  constructor(n) {
    this.nodes = Array.from({ length: n }, (_, i) => new Node(i));
  }

  addEdge(src, dst) {
    this.nodes[src].neighbors.push(dst);
    this.nodes[dst].neighbors.push(src);
  }

  buildFromEdges(edges) {
    for (const [src, dst] of edges) {
      this.addEdge(src, dst);
    }
    return this;
  }

  findPath(src, dst) {
    const visited = new Set([src]);
    const queue = [src];

    while (queue.length > 0) {
      const current = queue.shift();
      if (current === dst) {
        return true;
      } else {
        for (const neighbor of this.nodes[current].neighbors) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
    return false;
  }
}

function validPath(n, edges, source, destination) {
  return new Graph(n)
    .buildFromEdges(edges)
    .findPath(source, destination);
}

DFS方法

ほぼ一緒ですが、スタックなのでshiftではなくpopに変えるだけです。

// ...
  findPath(src, dst) {
    const visited = new Set([src]);
    const stack = [src];

    while (stack.length > 0) {
      const current = stack.pop(); // ここだけ違う
      if (current === dst) {
        return true;
      } else {
        for (const neighbor of this.nodes[current].neighbors) {
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            stack.push(neighbor);
          }
        }
      }
    }
    return false;
  }

再帰で書く場合は：

// ...
  dfs(current, dst, visited) {
    if (current === dst) {
      return true;
    }
    visited.add(current);
    for (const neighbor of this.nodes[current].neighbors) {
      if (!visited.has(neighbor)) {
        if (this.dfs(neighbor, dst, visited)) {
          return true;
        }
      }
    }
    return false;
  }

  findPath(src, dst) {
    const visited = new Set();
    return this.dfs(src, dst, visited);
  }

BFSとDFS探索は非常に重要な基礎なので、目を閉じても書けるようになりたいほどです。他の練習問題は下記のように上げました。

終わりに

今回はグラフの探索について、木と比較しながらまとめました。次回はUnion-Findについて書きます。

GitHubで編集を提案

Discussion