pta 7-1 图的深度优先遍历

图的深度优先遍历（Depth-First Search, DFS）是一种常用的图遍历方法，其基本思想是从图中某个顶点出发，按照深度优先的策略进行遍历，直到图中所有顶点都被访问为止。

下面是一个基于邻接表存储的图的深度优先遍历的 C++ 实现代码：

const int MAXN = 1005;

vector<int> G[MAXN]; // 存储图的邻接表
bool vis[MAXN];      // 标记每个顶点是否被访问过

void dfs(int u) {
    vis[u] = true; // 标记当前顶点已被访问
    cout << u << " "; // 输出当前访问的顶点编号
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (!vis[v]) { // 如果顶点 v 还未被访问，则继续搜索
            dfs(v);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入图的结点个数和边数
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v; // 输入一条边 (u, v)
        G[u].push_back(v);
        G[v].push_back(u); // 无向图需加入反向边
    }

    // 从结点 1 开始进行深度优先遍历
    dfs(1);

    return 0;
}

其中，`G[u]` 存储与结点 `u` 相邻的结点，`vis[u]` 表示结点 `u` 是否被访问过，`dfs(u)` 表示从结点 `u` 开始进行深度优先遍历。在 `dfs(u)` 中，我们首先将结点 `u` 标记为已访问，然后输出其编号，最后对于 `u` 的每个邻接结点 `v`，如果 `v` 还未被访问，则递归调用 `dfs(v)` 进行继续搜索。