深度优先搜索遍历c++

深度优先搜索（Depth First Search, DFS）是一种常见的图遍历算法，它可以用来解决许多问题，如连通性问题、最短路径问题、拓扑排序问题等。

以下是一个简单的深度优先搜索遍历的C++代码示例：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100; // 最大结点数
vector<int> G[MAXN]; // 图的邻接表表示
bool visited[MAXN]; // 记录结点是否已经访问

void dfs(int s) {
    stack<int> S; // 用栈来存储待访问的结点
    S.push(s); // 将起点压入栈中
    visited[s] = true; // 标记起点为已访问

    while (!S.empty()) {
        int u = S.top(); // 取出栈顶结点
        S.pop();

        // 遍历所有与 u 相邻的未访问结点
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (!visited[v]) {
                visited[v] = true; // 标记 v 为已访问
                S.push(v); // 将 v 压入栈中，待访问其相邻结点
            }
        }
    }
}

int main() {
    int n, m; // n 个结点，m 条边
    cin >> n >> m;

    // 读入图的边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u); // 若是无向图，则需要存储反向边
    }

    // 从结点 1 开始深度优先搜索
    dfs(1);

    return 0;
}

在这个代码示例中，我们采用了邻接表来表示图，使用栈来存储待访问的结点。对于每个还未访问的结点，我们将其压入栈中，并标记为已访问。然后遍历其所有相邻的未访问结点，再将这些相邻结点压入栈中。重复这个过程，直到栈为空。这样就完成了深度优先搜索遍历。

需要注意的是，在实际应用中，如果图非常大，使用递归实现的深度优先搜索可能会导致栈溢出。因此，建议使用如上述代码示例中所示的非递归实现方式。