面试算法：图的 BFS 与 DFS

图题通常先确定建图方式。

邻接表

std::vector<std::vector<int>> graph(n);
graph[u].push_back(v);

DFS

DFS 适合连通块、路径搜索、拓扑相关问题。

void dfs(int u) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) dfs(v);
    }
}

BFS

BFS 适合无权图最短步数。

访问标记必须及时设置，否则会重复入队。

建图比搜索更容易错

图题常常不是 DFS/BFS 写错，而是边建错。无向图要双向加边，有向图只加一个方向；网格图要检查边界；带权图需要保存权重。

DFS 适合“走到底”

DFS 适合枚举路径、判断连通块、做拓扑搜索。写递归 DFS 时，要注意递归深度。如果节点很多，可能需要改成显式栈。

BFS 适合“按层扩散”

迷宫最短路可以这样看：

queue.push(start);
dist[start] = 0;
while (!queue.empty()) {
    auto u = queue.front();
    queue.pop();
    for (auto v : next(u)) {
        if (!visited[v]) {
            visited[v] = true;
            dist[v] = dist[u] + 1;
            queue.push(v);
        }
    }
}

面试时怎么讲

先说明状态是什么，再说明邻居如何生成，最后说明 visited 在什么时候设置。这个顺序能减少很多重复访问和死循环问题。