用于在树或者图中寻找特定节点。

BFS 代码模板

generate_related_nodes 函数中会做两件事：

• 找到下一个节点；

• 判断该节点没有被访问过，才取出来。

visited = set()
def BFS(graph, start, end):
  queue = []
  queue.append([start])
  visited.add(start)

  while queue:
    node = queue.pop()
    visited.add(node)

    process(node)

    nodes = generate_related_nodes(node)
    queue.push(nodes)

  # other processing work
  ...

DFS 代码模板

递归写法：

visited = set()
def DFS(node, visited):
  visited.add(node)
  # process current node here
  ...
  for next_node in node.children():
    if not next_node in visited:
      DFS(next_node, visited)

迭代写法：

def DFS(self, tree):
  if tree.root is None:
    return []

  visited, stack = [], [tree.root]

  while stack:
    node = stack.pop()
    visited.add(node)

    process(node)
    nodes = generate_related_nodes(node)
    tack.push(node)

  # other processing work
  ...

岛屿数量

题目地址 (opens new window)

// DFS
const dfs = (grid, r, c) => {
  // 去除不合法的以及不是岛屿的点
  if (
    r < 0 ||
    r >= grid.length ||
    c < 0 ||
    c > grid[0].length ||
    grid[r][c] !== "1"
  ) {
    return;
  }
  // 访问过的岛屿置为 '0'
  grid[r][c] = "0";
  // 遍历该点的上下左右 4 个方向的点
  dfs(grid, r - 1, c);
  dfs(grid, r + 1, c);
  dfs(grid, r, c - 1);
  dfs(grid, r, c + 1);
};

const numIslands = (grid) => {
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") {
        dfs(grid, i, j);
        count++;
      }
    }
  }
  return count;
};

// DFS
const dfs = (grid, r, c) => {
  // 去除不合法的以及不是岛屿的点
  if (
    r < 0 ||
    r >= grid.length ||
    c < 0 ||
    c > grid[0].length ||
    grid[r][c] !== "1"
  ) {
    return;
  }
  // 访问过的岛屿置为 '0'
  grid[r][c] = "0";
  // 遍历该点的上下左右 4 个方向的点
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  for (let i = 0; i < 4; i++) {
    dfs(grid, r + dy[i], c + dx[i]);
  }
};

const numIslands = (grid) => {
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") {
        dfs(grid, i, j);
        count++;
      }
    }
  }
  return count;
};

// BFS
const bfs = (grid, r, c) => {
  const queue = [];
  queue.push([r, c]);
  while (queue.length) {
    [r, c] = queue.pop();
    if (
      r >= 0 &&
      r < grid.length &&
      c >= 0 &&
      c < grid[0].length &&
      grid[r][c] === "1"
    ) {
      grid[r][c] = "0";
      const dx = [-1, 1, 0, 0];
      const dy = [0, 0, -1, 1];
      for (let i = 0; i < 4; i++) {
        queue.push([r + dy[i], c + dx[i]]);
      }
    }
  }
};

const numIslands = (grid) => {
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") {
        bfs(grid, i, j);
        count++;
      }
    }
  }
  return count;
};