CC++ & Algorithm

图的DFS与BFS遍历：用两种方式逛游乐园

困难4
语言版本：C++
概述：把地图上的景点（节点）和道路（边）看作一张图，DFS和BFS都可以用来访问所有景点。

用两种方式逛游乐园：图的DFS与BFS遍历

想象一下，你和朋友去游乐园玩。游乐园里的每个游玩项目（比如摩天轮、过山车、旋转木马、海盗船、碰碰车）都是“景点”，景点之间有小路连接。你们想每个项目都玩一遍，但不想走回头路，也不想漏掉任何一个。这时候，你们需要一条路线——一个能访问所有景点的顺序。

计算机科学里，把景点看作“节点”，小路看作“边”，就构成了一张图（Graph）。图的遍历就是从某个节点出发，按照一定规则去访问所有能到达的节点。两种最常用的遍历方法是深度优先搜索（DFS） 和广度优先搜索（BFS）。它们逛游乐园的方式完全不同，但都能保证每个景点只去一次。

1. 游乐园地图：用邻接表存储图

在写代码之前，我们需要先把“地图”存进计算机。最常用的一种存储方式是邻接表：对于每个景点（节点），我们用一个列表记下它直接连接的那些景点（邻居）。

比如，假设游乐园有5个项目，编号0到4：

  • 0号：摩天轮
  • 1号：过山车
  • 2号：旋转木马
  • 3号：海盗船
  • 4号：碰碰车

它们之间的路是：0-1, 0-2, 1-3, 1-4。也就是说，从摩天轮可以走去过山车或旋转木马；从过山车又能走去海盗船和碰碰车。

用C++的vector数组表示邻接表：

vector<int> graph[5]; // graph[0]里存了{1,2}，graph[1]里存了{3,4}，等等

每个graph[i]就是一个列表，里面放着节点i的所有邻居的编号。如果图是无向的（路可以双向走），那么每条边都要在两个节点的列表里各出现一次。我们的例子中，为了简单只加了单向边（但实际遍历时方向不影响结果，只要能从0走到其他节点即可）。在真正的无向图里，需要加反向边。

2. 深度优先搜索（DFS）：先深入一个区域，再回头

DFS像这样逛游乐园：从入口的摩天轮出发，你直接走向它的第一个邻居——过山车。到了过山车，你发现它旁边还有海盗船和碰碰车，于是你选择先闯海盗船。到了海盗船，发现没有新项目了（或者说它的邻居都被访问过了），于是你退回过山车，再去碰碰车。碰碰车玩完后，再退回摩天轮，发现还有个旋转木马没去，于是去玩旋转木马。

这个过程就是走一条路走到黑，走不动了再回头。用专业术语说：DFS沿着一条路径一直深入，直到没有未访问的邻居，然后回溯到上一个节点，继续尝试其他邻居。

如何用代码实现DFS？

递归是最直观的方式。我们定义一个函数dfs(u)，表示“现在我在景点u，我要访问它，然后继续去访问我所有没去过的邻居”。

void dfs(int u, vector<bool>& visited) {
    visited[u] = true;                // 标记当前景点已访问
    cout << u << " ";                 // 输出当前景点编号（假装在玩）
    for (int v : graph[u]) {          // 遍历所有邻居v
        if (!visited[v]) {            // 如果邻居没去过
            dfs(v, visited);          // 就去拜访它（递归）
        }
    }
}

注意：递归之前必须先标记visited，否则可能会重复访问，甚至陷入死循环（如果图里有环）。

在上面的例子中，从0开始DFS，遍历顺序取决于邻居列表的顺序。因为graph[0]里先放进了1后放进2，所以会先走1那条分支。graph[1]里先放3后放4，所以从1先走3。结果就是：0→1→3→4→2。如果graph[0]里把2放在前面，顺序就会变成0→2→1→3→4。

使用栈的非递归DFS

DFS也可以不用递归，而用显式栈模拟。但递归写法简单直观，是CSP-J常用的方式。不过要小心，如果图很深（几万层），递归可能造成栈溢出。这时候就要用栈写循环版。这里先不展开。

3. 广度优先搜索（BFS）：一圈一圈向外扩散

BFS更像另一种玩法：你站在摩天轮（起点），先看看哪些项目是直接走一条路就能到的——哦，过山车和旋转木马。你决定先去玩这两个（顺序无所谓）。玩完它们之后，再从这两个出发，看它们又连接了哪些新项目——过山车连到海盗船和碰碰车，旋转木马没有新的邻居了。于是你接着去玩海盗船和碰碰车。就这么一圈一圈地往外扩散，就像水波一样。

BFS的核心是按层访问：先把离起点最近（距离为1）的节点全部访问，再访问距离为2的，以此类推。在无权图中，BFS第一次访问到某个节点时，走的路径就是最短路径（经过的边数最少）。

如何用代码实现BFS？

BFS需要借助队列（queue） 来记录“下一批要访问的节点”。过程是：

  1. 把起点放入队列，标记已访问。
  2. 只要队列不为空，就取出队首节点，访问它（比如输出编号）。
  3. 把它的所有未访问的邻居加入队列末尾，并标记它们已访问（标记要趁早，防止重复入队）。
void bfs(int start) {
    vector<bool> visited(N, false); // N是节点总数
    queue<int> q;                    // 队列，用来存“待访问的节点”
    q.push(start);                   // 起点入队
    visited[start] = true;           // 标记起点

    while (!q.empty()) {
        int u = q.front();           // 取出队首
        q.pop();                     // 弹出它
        cout << u << " ";            // 访问（游玩）该节点
        for (int v : graph[u]) {     // 遍历u的所有邻居
            if (!visited[v]) {       // 如果没去过
                visited[v] = true;   // 先标记（很重要！）
                q.push(v);           // 加入队列，稍后访问
            }
        }
    }
}

从0开始，BFS的顺序是：0 → 1, 2 → 3, 4。由于1和2都在同一层，谁先入队取决于graph[0]中邻居的顺序。如果1在2前面，结果就是0 1 2 3 4。

4. 常见错误（新手踩坑指南）

错误1：忘记标记已访问

如果没有在入队/入递归时立刻标记visited，可能会导致：

  • 重复入队，造成无限循环（尤其图中有环时）。
  • BFS中，同一个节点可能被多次加入队列，输出多次，效率低下甚至死循环。

正确做法：在加入队列之前就标记已访问，或者在递归函数一开始就标记。

错误2：只从一个起点出发，忽略多个连通分量

如果图不是连通的（比如游乐园被分成两个独立区域，中间没有路），上面的代码只从0开始，永远走不到另一个区域的景点。例如，图中有节点0-1-2和节点3-4（两边不连通）。那么从0出发DFS只能访问0,1,2，漏掉了3,4。

解决办法：在主函数里，对所有节点循环，只要没访问过，就把它作为起点调用DFS或BFS。

vector<bool> visited(N, false);
for (int i = 0; i < N; i++) {
    if (!visited[i]) {
        cout << "从" << i << "开始的新连通分量: ";
        dfs(i, visited);
        cout << endl;
    }
}

错误3：邻接表忘记加反向边（无向图）

如果图是无向的，在构建图时，每条边必须加两次（graph[a].push_back(b); graph[b].push_back(a);）。如果只加一次，比如只加了0->1没加1->0，那么从1出发就找不到0，遍历就会出错。

错误4：递归DFS的栈溢出

当图很深（比如有10000个节点排成一条直线），递归会调用10000层，可能超出默认的栈大小。在CSP-J中一般不会遇到大规模数据，但了解这个问题总没错。解决方案是用BFS或非递归DFS（用栈模拟）。

5. 完整可运行的示例代码

下面我们给出一个完整的C++程序，它使用邻接表存储一个无向图（5个节点，边为0-1,0-2,1-3,1-4），并用DFS和BFS分别遍历，最后输出遍历顺序。同时，为了展示多连通分量的处理，我们再添加一个孤立的节点5，并单独处理它。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 6;                      // 节点总数：0~5
vector<int> graph[N];                 // 邻接表

// DFS 递归遍历（从节点u开始）
void dfs(int u, vector<bool>& visited) {
    visited[u] = true;                // 标记当前节点已访问
    cout << u << " ";                 // 输出节点编号
    for (int v : graph[u]) {          // 遍历所有邻居
        if (!visited[v]) {            // 如果邻居没去过
            dfs(v, visited);          // 递归深入
        }
    }
}

// BFS 遍历（从节点start开始）
void bfs(int start) {
    vector<bool> visited(N, false);   // 记录哪些节点已访问
    queue<int> q;                     // 队列存“待访问节点”
    q.push(start);                    // 起点入队
    visited[start] = true;            // 标记起点

    while (!q.empty()) {
        int u = q.front();            // 取队首
        q.pop();                      // 弹出
        cout << u << " ";             // 访问节点
        for (int v : graph[u]) {      // 遍历邻居
            if (!visited[v]) {
                visited[v] = true;    // 先标记
                q.push(v);            // 入队等待访问
            }
        }
    }
}

int main() {
    // 构建无向图：每条边加两次
    graph[0].push_back(1);            // 0号摩天轮连接1号过山车
    graph[1].push_back(0);            // 反过来也要加
    graph[0].push_back(2);            // 0连接2号旋转木马
    graph[2].push_back(0);
    graph[1].push_back(3);            // 1连接3号海盗船
    graph[3].push_back(1);
    graph[1].push_back(4);            // 1连接4号碰碰车
    graph[4].push_back(1);
    // 节点5是孤立的，没有边

    // 用DFS遍历整个图（包括孤立节点）
    cout << "DFS遍历顺序（全图）: ";
    vector<bool> visited(N, false);
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            cout << "[分量起点" << i << "] "; // 标记新连通分量
            dfs(i, visited);
        }
    }
    cout << endl;

    // 用BFS遍历整个图（包括孤立节点）
    cout << "BFS遍历顺序（全图）: ";
    visited.assign(N, false);          // 重置visited
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            cout << "[分量起点" << i << "] ";
            bfs(i);
        }
    }
    cout << endl;

    return 0;
}

输出结果（可能因编译器入队顺序略有不同）：

DFS遍历顺序（全图）: [分量起点0] 0 1 3 4 2 [分量起点5] 5 
BFS遍历顺序（全图）: [分量起点0] 0 1 2 3 4 [分量起点5] 5

可以看到，DFS先走深再回溯，BFS一层一层走。节点5单独成一个分量。

6. 怎么选择用DFS还是BFS？

  • DFS：适合用来解决“有没有路径”“图是否连通”“是否存在环”“拓扑排序”等问题。它实现简单（递归），而且可以配合回溯进行路径记录。缺点是不容易找到最短路径（但能找出一条路径）。

  • BFS：在无权图中，BFS第一次到达某个节点时走的路径就是最短路径（边数最少）。因此求最短路径、求两点间距离等场景优先用BFS。另外BFS天然按层访问，适合处理层序问题（比如二叉树层序遍历）。缺点是需要队列，空间消耗可能比DFS大（但一般不大）。

如果你只是想单纯访问所有节点，两者都可以。但如果你需要找“从家到学校最少经过几条路”，那就应该用BFS。

7. 相关知识点指引

掌握了图的DFS和BFS遍历后，你可以进一步学习：

  • 图的连通性：如何判断整个图有几个连通分量？上面代码已经展示了方法。
  • 最小生成树：Kruskal算法（需要并查集）和Prim算法（类似BFS思想）。
  • 最短路径：BFS用于无权图，Dijkstra用于带正权图，Bellman-Ford用于有负权图。
  • 拓扑排序：对有向无环图（DAG）进行DFS，得到逆后序。
  • 二分图判定：用BFS/DFS染色判定。

另外，如果你对递归理解还不够，可以先练习用递归遍历二叉树，因为二叉树的DFS和BFS是图遍历的特殊情形。

现在，你可以试着用这两种方法去“逛”更多的图了——比如学校里各教室之间的路线图，或者游戏地图中的任务点。看懂遍历，就是看懂地图的第一步！

例题精讲

1单选题

关于图的深度优先遍历（DFS）和宽度优先遍历（BFS），以下说法正确的是？

ADFS使用队列实现，BFS使用栈实现
BDFS和BFS都能用于判断图是否连通
CDFS保证找到最短路径，BFS不一定
DBFS遍历图时，每个节点只被访问一次，而DFS可能重复访问
2判断题

在图的广度优先遍历中，如果使用邻接表存储，则时间复杂度为O(V+E)。

3填空题
以下DFS函数用于遍历连通图，使用邻接表存储。请补全代码。
void DFS(int u, vector<bool>& visited, const vector<vector<int>>& adj) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (___) {
            DFS(v, visited, adj);
        }
    }
}