对于非连通图的深度优先搜索 C++代码

对于非连通图的深度优先搜索，我们需要对每一个未被访问过的连通块都进行深度优先搜索。以下是C++代码实现：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;  // 点数的最大值
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]) {
            dfs(v);  // 递归访问未被访问过的节点
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;  // 输入点数和边数
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;  // 输入一条边的两个端点
        G[u].push_back(v);  // 添加边
        G[v].push_back(u);  // 无向图需要添加反向边
    }
    // 对每个未被访问过的连通块进行深度优先搜索
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }

    return 0;
}

在上述代码中，我们用邻接表表示图，用bool类型的vis数组标记每个点是否被访问过。在深度优先搜索中，我们先标记当前节点已被访问，并输出该节点，然后递归访问该节点的所有未被访问过的邻居节点。最后，对每个未被访问过的连通块进行深度优先搜索，即可遍历整个图。