如何使用C++实现深度优先搜索遍历无向连通图G并输出访问过的所有节点？

在C++中，你可以使用递归的方式来实现深度优先搜索（DFS）。以下是基本步骤：

1. 定义一个函数`dfs(graph, start, visited)`，其中`graph`是邻接列表表示的无向图，`start`是起始节点，`visited`是一个布尔数组用于记录已访问的节点。

bool visited[vertices]; // vertices是图中的顶点数

void dfs(vector<vector<int>>& graph, int node) {
    if (visited[node]) return; // 如果节点已访问过，则跳过
    visited[node] = true; // 标记当前节点已访问
    
    cout << node << " "; // 输出当前节点

    // 遍历邻居节点
    for (int neighbor : graph[node]) {
        dfs(graph, neighbor); // 对未访问的邻居递归调用dfs
    }
}

2. 调用`dfs(graph, start_node)`，`start_node`是你想从哪个节点开始遍历的节点。

这里假设`graph`是以邻接表的形式存储的，每个元素`graph[i]`包含的是与节点i相邻的所有节点的集合。`vertices`变量存储了图中节点的数量。

相关问题

1.给定一个无向连通图G，采用深度优先搜索方式访问图中节点，并输出。用c++

以下是使用C++实现深度优先搜索遍历无向连通图并输出的代码：

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

using namespace std;

// 定义无向图类
class Graph {
public:
    Graph(int n) : nodes(n), edges(n) {}

    // 添加边
    void addEdge(int u, int v) {
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    // 深度优先搜索遍历
    void dfs(int start) {
        vector<bool> visited(nodes, false); // 记录节点是否被访问过
        stack<int> s; // 使用栈来实现深度优先搜索

        s.push(start);
        visited[start] = true;
        cout << start << " ";

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

            for (int neighbor : edges[cur]) {
                if (!visited[neighbor]) {
                    s.push(neighbor);
                    visited[neighbor] = true;
                    cout << neighbor << " ";
                }
            }
        }
    }

private:
    int nodes; // 节点数
    vector<vector<int>> edges; // 邻接表表示的边
};

int main() {
    // 构造一个无向图
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    g.addEdge(3, 5);

    // 从节点0开始深度优先搜索遍历
    g.dfs(0);

    return 0;
}

输出结果为：0 1 3 4 2 5

3.给定一个无向连通图G，采用广度优先搜索方式访问图中节点，并输出。用c++

以下是使用C++实现广度优先搜索遍历无向连通图的代码：

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

const int MAXN = 100; // 最大节点数
vector<int> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记节点是否被访问过

void bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " "; // 输出节点
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (!vis[v]) {
                q.push(v);
                vis[v] = true;            }
        }
    }
}

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); // 无向图需要双向加边
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            bfs(i); // 从未被访问的节点开始遍历
        }
    }
    return 0;
}