C++ 深度优先搜索算法实现详解

以下是用C++编写的深度优先搜索算法的示例代码：

#include<iostream>
#include<list>
using namespace std;

// 图的类定义
class Graph {
    int V; // 顶点的数量
    list<int> *adj; // 邻接表

    // 递归函数，用于深度优先搜索
    void DFSUtil(int v, bool visited[]) {
        // 标记当前顶点为已访问
        visited[v] = true;
        cout << v << ' '; 

        // 递归访问与当前顶点相邻的未访问顶点
        for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
            if (!visited[*i])
                DFSUtil(*i, visited);
    }

public:
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }

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

    // 深度优先搜索
    void DFS(int v) {
        // 创建一个标记数组，用于跟踪访问状态
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // 从指定的顶点开始执行递归函数
        DFSUtil(v, visited);
    }
};

int main() {
    // 创建一个图对象
    Graph g(6);
    // 添加边
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(2, 5);

    cout << "深度优先遍历结果：";
    g.DFS(0);

    return 0;
}

这段代码实现了一个简单的图类和深度优先搜索功能。在main函数中，我们创建了一个具有6个顶点的图，并添加了一些边。然后，我们调用DFS方法，从顶点0开始执行深度优先搜索。搜索结果将打印在控制台上。

深度优先搜索算法的原理

深度优先搜索算法是一种图遍历算法，它从一个顶点开始，沿着一条路径一直走下去，直到这条路径的尽头，然后再回溯到上一个节点，继续探索其他路径。这种算法就像在迷宫中探索，总是选择一条路径走到头，然后再折返回来，寻找其他路径。

代码解析

图的类定义

V 表示图的顶点数
adj 是一个邻接表，用于存储图中的边信息
DFSUtil 是一个递归函数，用于实现深度优先搜索算法

添加边

addEdge 函数用于在图中添加边

深度优先搜索

DFS 函数用于执行深度优先搜索算法，它首先创建一个标记数组，用于跟踪访问状态，然后调用 DFSUtil 函数进行递归搜索。

总结

深度优先搜索算法是一种常用的图遍历算法，它在许多领域都有应用，例如路径规划、拓扑排序、迷宫求解等。本文通过代码示例和原理讲解，帮助你更好地理解和掌握深度优先搜索算法。