使用C++实现图的深度优先遍历方法

深度优先遍历（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索图的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

以下是使用C++实现图的深度优先遍历方法：

1. 定义一个邻接表表示图；
2. 创建一个访问标记数组，用于记录每个节点是否被访问过；
3. 从一个未访问的节点开始，递归地访问其邻居节点；
4. 当所有节点都被访问过后，算法结束。

#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 << endl;

        for (int i = 0; i < graph[node].size(); ++i) {
            int neighbor = graph[node][i];
            if (!visited[neighbor]) {
                s.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    // 创建邻接表表示图
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 4, 5},
        {1},
        {1, 2},
        {2}
    };

    // 创建访问标记数组
    vector<bool> visited(graph.size(), false);

    // 从节点0开始深度优先遍历
    dfs(0, graph, visited);

    return 0;
}

这段代码中，`dfs`函数实现了深度优先遍历算法。`main`函数中创建了一个邻接表表示的图，并调用`dfs`函数进行遍历。