PP4886 图的遍历（不一定连通）（基础）

这道题要我们分别用"深度优先遍历"（DFS）和"广度优先遍历"（BFS）走遍一张无向图，并且图不一定是连通的。理解两种遍历的区别是解题的关键。

解题思路

第一步，理解深度优先遍历。 DFS 就像在迷宫里"一条路走到黑"：从 1 出发，先走向编号最小的邻居，到了新结点再继续往深处走，走到没有没走过的邻居时，退回上一个结点找别的路。样例里 1 先走到 2，2 走到 4，4 没有新邻居退回，2 也没有新邻居退回，1 再走到 3，所以结果是 1-2-4-3。

第二步，理解广度优先遍历。 BFS 像"水波一层层扩散"：先把 1 的所有邻居 2、3 都访问到，再去访问这些邻居的邻居 4，所以结果是 1-2-3-4。实现时用队列：从队头取出一个结点，把它没访问过的邻居按编号从小到大排着入队。

第三步，处理不连通的情况。 题目特别说明图不一定连通。我写一个主循环从 1 到 n 依次扫描，只要发现还有结点没被访问过，就从它开始再启动一次 DFS（或 BFS），这样能保证把每个连通块都遍历完。输出时这些结点会按访问顺序连在一起。

第四步，输出格式。 深度遍历结果占第一行，广度遍历结果占第二行，每个结点之间用 '-' 符号连接，比如 1-2-4-3。

第五步，注意细节。 邻接矩阵存图，访问数组标记是否走过；因为要优先访问编号小的结点，找邻居时内层循环从 1 到 n 从小到大找；BFS 用数组模拟队列，注意队头和队尾指针别写反。

参考代码

// 输出无向图的深度遍历和广度遍历结果，从1开始，优先编号低的，用-分隔
#include <iostream>
using namespace std;

int a[505][505]; // 邻接矩阵
int vis[505];    // 访问标记
int out[505];    // 遍历结果
int que[505];    // BFS队列
int n, m, top;

void dfs(int u) {
    vis[u] = 1;
    out[++top] = u;
    for (int v = 1; v <= n; v++) // 优先编号低
        if (a[u][v] && !vis[v]) dfs(v);
}

void bfs() {
    int head = 0, tail = 0;
    for (int i = 1; i <= n; i++) vis[i] = 0; // 重新清标记
    top = 0;
    for (int s = 1; s <= n; s++) { // 保证遍历所有连通块
        if (vis[s]) continue;
        vis[s] = 1;
        que[tail++] = s;
        while (head < tail) {
            int u = que[head++];
            out[++top] = u;
            for (int v = 1; v <= n; v++)
                if (a[u][v] && !vis[v]) {
                    vis[v] = 1;
                    que[tail++] = v;
                }
        }
    }
}

void print() {
    for (int i = 1; i <= top; i++) {
        if (i > 1) cout << "-";
        cout << out[i];
    }
    cout << endl;
}

int main() {
    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;
    }
    for (int s = 1; s <= n; s++) // 从1开始，含不连通部分
        if (!vis[s]) dfs(s);
    print();
    bfs();
    print();
    return 0;
}

复杂度分析

复杂度分析：用邻接矩阵实现时，找邻居要扫描整行，深度和广度遍历的时间都是 O(n²)，空间 O(n²)。n 是结点数，m 是边数，规模不大，两种遍历都能瞬间完成。