P4877 图的遍历（连通图）（基础）

解题思路

第一步，理解题目要求。 给一个无向连通图，从编号 1 出发，输出深度优先遍历和广度优先遍历的结果，结点之间用"-"隔开，并且优先访问编号小的结点。

第二步，保存图。 结点数最多 100，用邻接矩阵 g[a][b] 存边：a、b 有边就令 g[a][b]=g[b][a]=1。无向图两边都要记。扫一个结点的邻居时从 1 到 n 扫一遍，自然保证从小到大。

第三步，深度优先遍历。 写递归函数 dfs(u)：先标记并输出 u，再从编号 1 到 n 找 u 的邻居，没访问过就递归。邻居从小到大扫描，保证编号小的优先。一条路走到底再回头，就是深度优先。

第四步，广度优先遍历。 用数组模拟队列。把起点 1 放入队列并标记，每次取出队首 u，把 u 所有没访问过的邻居从小到大放进队列并标记。先访问离起点近的结点，一层层往外扩展，就是广度优先。

第五步，注意输出格式。 第一个结点前不能有"-"。输出时判断：如果不是起点 1，就先输出一个"-"。深度和广度各输出一行。

举个例子。 样例边 1-2、1-3、2-4。深度优先：从 1 出发先到 2，再到 4，回退后访问 3，得到 1-2-4-3；广度优先：先访问 1，放入 2、3，出队 2 访问到 4，再出队 3，得到 1-2-3-4，与样例一致。

边界情况。 图保证连通，所以两种遍历都能访问所有结点。如果 n=1，只输出一个 1，程序也能正确处理。

参考代码

// 图的深度和广度遍历：邻接矩阵存图，编号小优先，输出用-连接
#include <iostream>
using namespace std;

int g[105][105];  // 邻接矩阵
int vis[105];     // 访问标记
int n;

// 深度优先遍历
void dfs(int u) {
    vis[u] = 1;
    if (u != 1) cout << '-';
    cout << u;
    for (int v = 1; v <= n; v++)
        if (g[u][v] && !vis[v]) dfs(v);
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;   // 无向图
    }
    dfs(1);
    cout << endl;
    for (int i = 1; i <= n; i++) vis[i] = 0;
    int q[105], head = 0, tail = 0;
    q[tail++] = 1;
    vis[1] = 1;
    while (head < tail) {
        int u = q[head++];
        if (u != 1) cout << '-';
        cout << u;
        for (int v = 1; v <= n; v++)
            if (g[u][v] && !vis[v]) { vis[v] = 1; q[tail++] = v; }
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度。 深度和广度遍历都访问 n 个结点，每个结点扫一遍邻居列表（长 n），所以每个遍历 O(n²)，两次遍历合计 O(n²)。n 最大 100，n² 只有 10000，非常快。

空间复杂度。 邻接矩阵 O(n²)，访问标记和队列都是 O(n)，总空间复杂度 O(n²)。