图的表示与 DFS / BFS

// 运行环境：Node.js 14+
// 保存为 dsa-l15.js，执行：node dsa-l15.js

// 邻接表建无向图
function buildGraph(edges) {
  const g = new Map()
  const add = (a, b) => { if (!g.has(a)) g.set(a, []); g.get(a).push(b) }
  for (const [a, b] of edges) { add(a, b); add(b, a) } // 无向：双向
  return g
}

// DFS（递归）
function dfs(g, start, visited = new Set()) {
  visited.add(start)
  const order = [start]
  for (const nxt of (g.get(start) || [])) {
    if (!visited.has(nxt)) order.push(...dfs(g, nxt, visited))
  }
  return order
}

// BFS（队列）
function bfs(g, start) {
  const visited = new Set([start])
  const q = [start], order = []
  while (q.length) {
    const cur = q.shift()
    order.push(cur)
    for (const nxt of (g.get(cur) || [])) {
      if (!visited.has(nxt)) { visited.add(nxt); q.push(nxt) }
    }
  }
  return order
}

const g = buildGraph([['A','B'],['A','C'],['B','D']])
console.log('DFS', dfs(g, 'A')) // ['A','B','D','C']（路径依赖）
console.log('BFS', bfs(g, 'A')) // ['A','B','C','D']（逐层）

function numIslands(grid) {
  const m = grid.length, n = grid[0].length
  let count = 0
  const sink = (i, j) => {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] !== '1') return
    grid[i][j] = '0' // 淹没，防止重复访问
    sink(i+1,j); sink(i-1,j); sink(i,j+1); sink(i,j-1)
  }
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === '1') { count++; sink(i, j) }
  return count
}