GESP 七级 · GESP 202503 C++ 七级 第 9 题

给定一个无向图，图的节点编号从 $0$ 到 $n-1$，图的边以邻接表的形式给出。下面的程序使用深度优先搜索（DFS）遍历该图，并输出遍历的节点顺序。横线处应填入的是（ ）。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void DFS(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    stack<int> s;
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        cout << node << " "; // 输出当前节点

        // 遍历邻接节点
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                // 在此处填入代码
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<bool> visited(n, false);

    // 从节点 0 开始DFS遍历
    DFS(0, graph, visited);

    return 0;
}

A.

visited[neighbor] = true;
s.push(neighbor - 1);

B.

visited[neighbor] = true;
s.push(neighbor + 1);

C.

visited[neighbor] = false;
s.push(neighbor);

D.

visited[neighbor] = true;
s.push(neighbor);

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

模拟执行时注意：① 循环变量的起始和终止值；② 递归的边界条件；③ 数据类型转换和精度问题。

【考点】深度优先搜索（DFS）遍历｜栈（stack）模拟递归｜visited 数组标记访问状态

1. 🎯 考纲定位（考点定位）

GESP 七级 图论模块，核心考点深度优先搜索（DFS）遍历。命题人卡住的是考生对"递归转迭代"的理解——很多人会直接套用递归写法，却忘记迭代版必须用栈模拟调用过程，且访问标记要前置。