Chapter 94

深さ優先探索

miku
miku
2021.11.20に更新

深さ優先探索

深さ優先探索では探索を開始する頂点を選択し、その頂点に繋がっている別の頂点に移動、その頂点から更に繋がっている頂点に移動・・・と、ひたすら奥に向かって探索を進める。繋がっている頂点が無くなった場合、元の道を戻り、別の方向を選び、また奥に向かって探索を行う。

上記のようなグラフを用意して、探索を開始する頂点を 1 とする。

  • ある方向に向かってひたすら探索をしたいので、今回は左側に向かって 1-2-6 と進む。
  • 6 より奥の頂点は存在しないので、2 まで戻り、別のルートである 5 まで進む。
  • 5 より奥の頂点は存在しないので、1 まで戻り、別のルートである 3 まで進む。
  • 3 より奥の頂点は存在しないので、1 まで戻り、別のルートである 4-7 と進む。

上記手順をコードに落とすための具体的なアルゴリズムは下記のとおり。

  1. 始点を配列に加える。
  2. 配列から末尾にある頂点を取り出す。
  3. 取り出した頂点につながっている未探索の頂点を全て配列の末尾に追加する。
  4. 配列の中身が空なら処理を終了、そうでなければ 2 に戻る。

幅優先探索では配列に入れたものを先に取り出す形だったが、深さ優先探索では先に入れたものを後に取り出す形になる。この処理以外は幅優先探索と全く同じアルゴリズムになる。

深さ優先探索で得られる経路は、幅優先探索と違い、最短経路であると保証はされない。ただし、目的地までのルートが1つしかない場合は必然的に最短経路になる。このような全ての頂点間のルートが1つしかないグラフのことを木と呼ぶ。

深さ優先探索を行うコード

const n = 8;
const edge = [[1, 2, 3], [4, 5], [0], [0, 6], [1], [1], [3], []];

function dfs(start) {
  const seen = new Array(n).fill(false);
  seen[start] = true;
  const stack = [start];

  while (stack.length > 0) {
    const cur = stack.pop();
    console.log(cur);

    for (const next of edge[cur]) {
      if (seen[next]) continue;
      seen[next] = true;

      stack.push(next);
    }
  }
}

dfs(0);

再帰を利用した深さ優先探索

const n = 8;
const edge = [[1, 2, 3], [4, 5], [0], [0, 6], [1], [1], [3], []];

const seen = new Array(n).fill(false);

function dfs(cur) {
  seen[cur] = true;
  console.log(cur);

  for (const next of edge[cur]) {
    if (seen[next]) continue;
    dfs(next);
  }
}

dfs(0);

二次元配列での深さ優先探索

const INF = 1000000000;
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const W = 4;
const H = 4;
const WALL = 1;
const map = [
  [0, 0, 1, 0],
  [0, 1, 1, 0],
  [0, 1, 1, 0],
  [0, 0, 0, 0],
];

function dfs(sx, sy, gx, gy) {
  const dist = Array(H)
    .fill()
    .map(() => Array(W).fill(INF));

  dist[sy][sx] = 0;

  const stack = [{ x: sx, y: sy }];

  while (stack.length > 0) {
    const cur = stack.pop();

    if (cur.x === gx && cur.y === gy) break;

    for (let i = 0; i < 4; i++) {
      const tx = cur.x + dx[i];
      const ty = cur.y + dy[i];

      if (tx < 0 || tx >= W || ty < 0 || ty >= H) continue;
      if (map[ty][tx] === WALL) continue;
      if (dist[ty][tx] !== INF) continue;

      dist[ty][tx] = dist[cur.y][cur.x] + 1;
      stack.push({ x: tx, y: ty });
    }
  }

  return dist[gy][gx];
}

console.log(dfs(1, 0, 1, 3)); // 4
console.log(dfs(1, 0, 3, 0)); // 10

経路を求める

const INF = 1000000000;
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const W = 4;
const H = 4;
const WALL = 1;
const map = [
  [0, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 1, 0, 1],
  [0, 0, 0, 0],
];

function bfs(sx, sy, gx, gy) {
  const prev = [];
  const dist = Array(H)
    .fill()
    .map(() => Array(W).fill(INF));
  dist[sy][sx] = 0;

  const stack = [{ x: sx, y: sy }];
  while (stack.length > 0) {
    const cur = stack.pop();

    if (cur.x === gx && cur.y === gy) break;

    for (let i = 0; i < 4; i++) {
      const tx = cur.x + dx[i];
      const ty = cur.y + dy[i];

      if (tx < 0 || tx >= W || ty < 0 || ty >= H) continue;
      if (map[ty][tx] === WALL) continue;
      if (dist[ty][tx] !== INF) continue;

      dist[ty][tx] = dist[cur.y][cur.x] + 1;
      stack.push({ x: tx, y: ty });
      prev[ty * W + tx] = cur;
    }
  }

  let routes = [];
  let cx = gx;
  let cy = gy;

  while (true) {
    routes.unshift({ x: cx, y: cy });

    if (cx === sx && cy === sy) {
      break;
    }

    const index = cy * W + cx;
    const p = prev[index];
    cx = p.x;
    cy = p.y;
  }

  return routes;
}

/*
0: {x: 0, y: 0}
1: {x: 1, y: 0}
2: {x: 2, y: 0}
3: {x: 2, y: 1}
4: {x: 2, y: 2}
5: {x: 2, y: 3}
6: {x: 1, y: 3}
7: {x: 0, y: 3}
8: {x: 0, y: 2}
*/
console.log(bfs(0, 0, 0, 2));

深さ優先探索の可視化

const Cell = {
  Floor: "floor",
  Wall: "wall",
};

const INF = 1000000000;
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const cellSize = 10;
const Colors = {
  Visited: "#1c8b94",
  Routes: "#de980f",
  StartGoal: "#cd3830",
  Wall: "#757161",
};
const mapString = `
###########################
#############S#############
#############_#############
#############_#############
#############_#############
#############_#############
#G________________________#
#############_#############
###########_____###########
##########__#_#__##########
#########__##_##__#########
########__###_###__########
#######__####_####__#######
######__#####_#####__######
#####__######_######__#####
####__#######_#######__####
###__########_########__###
##__#########_#########__##
#__##########_##########__#
#############_#############
#############_#############
#############_#############
#############_#############
#############_#############
#############_#############
#############_#############
###########################
`;

let map, w, h, sx, sy, gx, gy, stack, dist, prevs, visited, routes, isPlaying;

function setup() {
  createCanvas(windowWidth, windowHeight);

  parseStringMap();

  stack = [{ x: sx, y: sy }];
  prevs = [];
  visited = [];
  dist = [];
  for (let y = 0; y < map.length; y++) {
    dist[y] = new Array(map[0].length).fill(INF);
  }
  dist[sy][sx] = 0;

  while (0 < stack.length) {
    const cur = stack.pop();
    visited.push(cur);

    if (cur.x === gx && cur.y === gy) break;

    for (let i = 0; i < 4; i++) {
      const tx = cur.x + dx[i];
      const ty = cur.y + dy[i];

      if (!(0 <= tx && tx < w && 0 <= ty && ty < h)) continue;
      if (map[ty][tx] === Cell.Wall) continue;
      if (dist[ty][tx] !== INF) continue;

      dist[ty][tx] = dist[cur.y][cur.x] + 1;
      stack.push({ x: tx, y: ty });
      prevs[ty * w + tx] = cur;
    }
  }

  routes = [];
  let cx = gx;
  let cy = gy;

  while (true) {
    routes.unshift({ x: cx, y: cy });
    if (cx === sx && cy === sy) {
      break;
    }
    const index = cy * w + cx;
    const prev = prevs[index];
    cx = prev.x;
    cy = prev.y;
  }

  initFill();
  const c = Colors.StartGoal;
  fillCell(sx, sy, c);
  fillCell(gx, gy, c);
  isPlaying = true;
}

function draw() {
  if (isPlaying) {
    if (visited.length > 0) {
      const cur = visited.shift();
      const [cx, cy] = [cur.x, cur.y];
      if ((cx == sx && cy == sy) || (cx == gx && cy == gy)) {
        return;
      }
      fillCell(cx, cy, Colors.Visited);
    } else if (routes.length > 0) {
      const cur = routes.shift();
      const [cx, cy] = [cur.x, cur.y];
      if ((cx == sx && cy == sy) || (cx == gx && cy == gy)) {
        return;
      }
      fillCell(cx, cy, Colors.Routes);
    }
  }
}

function parseStringMap() {
  map = [];
  const ms = mapString.split("\n");
  ms.shift();
  ms.pop();

  h = ms.length;
  w = ms[0].length;

  for (let y = 0; y < h; y++) {
    map[y] = [];
    for (let x = 0; x < w; x++) {
      switch (ms[y][x]) {
        case "_":
          map[y][x] = Cell.Floor;
          break;
        case "S":
          sx = x;
          sy = y;
          map[y][x] = Cell.Floor;
          break;
        case "G":
          gx = x;
          gy = y;
          map[y][x] = Cell.Floor;
          break;
        default:
          map[y][x] = Cell.Wall;
          break;
      }
    }
  }
}

function initFill() {
  clear();
  strokeWeight(1);

  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      if (map[y][x] === Cell.Wall) {
        fillCell(x, y, Colors.Wall);
      }
    }
  }
}

function fillCell(x, y, c) {
  fill(c);
  const tx = x * cellSize;
  const ty = y * cellSize;
  rect(tx, ty, cellSize, cellSize);
}