DFS：图的连通性与遍历

一、面试常考点

1. 如何统计连通分量

遍历所有节点，未访问节点发起一次 DFS，计数加一。

2. 如何防止重复访问

使用 visited 集合或数组。

二、细节介绍

1. 邻接表建图

稀疏图优先邻接表，空间更省。

2. 无向图遍历

双向建边，访问时靠 visited 防回头。

三、示例代码

function countComponents(n, edges) {
  const g = Array.from({ length: n }, () => [])
  for (const [u, v] of edges) {
    g[u].push(v)
    g[v].push(u)
  }

  const visited = Array(n).fill(false)

  function dfs(u) {
    visited[u] = true
    for (const v of g[u]) {
      if (!visited[v]) dfs(v)
    }
  }

  let count = 0
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i)
      count++
    }
  }
  return count
}

四、常用应用场景

1. 社交网络社区划分

统计用户关系图中的连通块。

2. 服务依赖分组

识别互相可达的服务子图。