深度优先搜索（DFS）算法 c++

深度优先搜索（DFS）是一种用于图和树的遍历算法，它按照深度优先的方式进行搜索。在DFS算法中，我们从一个起始节点开始，沿着一条路径一直向下搜索，直到达到最深的节点，然后回溯到上一个节点，继续搜索其他路径，直到找到问题的解或者遍历完所有可能的路径。

以下是一个使用C++实现深度优先搜索算法的示例：

#include <iostream>
#include <vector>

using namespace std;

// 定义图的邻接表表示
class Graph {
private:
    int V; // 图的顶点数
    vector<vector<int>> adj; // 邻接表

public:
    Graph(int v) {
        V = v;
        adj.resize(V);
    }

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

    // 深度优先搜索
    void DFS(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";

        // 递归访问邻接节点
        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
            if (!visited[u]) {
                DFS(u, visited);
            }
        }
    }

    // 对图进行深度优先搜索
    void DFS() {
        vector<bool> visited(V, false); // 记录节点是否被访问过

        // 从每个未被访问的节点开始进行DFS
        for (int v = 0; v < V; v++) {
            if (!visited[v]) {
                DFS(v, visited);
            }
        }
    }
};

int main() {
    // 创建一个包含5个节点的图
    Graph g(5);

    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);

    // 对图进行深度优先搜索
    cout << "DFS traversal: ";
    g.DFS();

    return 0;
}

输出结果为：

DFS traversal: 0 1 3 4 2

这是一个简单的深度优先搜索算法的示例，它通过邻接表表示图，并从每个未被访问的节点开始进行深度优先搜索。在搜索过程中，我们使用一个visited数组来记录节点是否被访问过，以避免重复访问。