图的dfs 邻接表版本

图论 C++ 公开

#include <cstdio>
#include <vector>
using namespace std;

const int N = 1005;
int n, m;
vector<int> g[N];    // g[x]:点 x 的所有邻居(邻接表)
bool visited[N];     // visited[x]:点 x 来过没有

void dfs(int x) {
    visited[x] = true;                         // 1. 打记号:x 来过了
    printf("%d ", x);                          //    记入访问顺序
    for (int i = 0; i < (int)g[x].size(); i++) {   // 2. 依次看 x 的每个邻居
        int y = g[x][i];
        if (!visited[y]) {                     // 3. 没来过,才往深处走
            dfs(y);
        }
    }
}                                              // 4. 邻居都看完了,函数结束,自动返回上一层

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);                     // 无向图,两个方向都要存
        g[v].push_back(u);
    }
    dfs(1);
    printf("\n");
    return 0;
}