图的dfs 矩阵版本

图论 C++ 公开

#include <cstdio>
using namespace std;

const int N = 1005;
int n, m;
int g[N][N];         // g[x][y] = 1 表示 x 和 y 之间有边(邻接矩阵)
bool visited[N];     // visited[x]:点 x 来过没有

void dfs(int x) {
    visited[x] = true;                         // 1. 打记号:x 来过了
    printf("%d ", x);                          //    记入访问顺序
    for (int y = 1; y <= n; y++) {             // 2. 扫描第 x 行,从左到右检查每个格子
        if (g[x][y] == 1 && !visited[y]) {     // 3. 有边,而且 y 没来过,才往深处走
            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][v] = 1;                           // 无向图,两个方向都要填 1
        g[v][u] = 1;
    }
    dfs(1);
    printf("\n");
    return 0;
}