C++ 实现深度优先搜索（DFS）的简单示例代码
C++ 实现深度优先搜索（DFS）的简单示例代码
#include <iostream>
#include <vector>
#include <stack>/**C++ 实现深度优先搜索（DFS）的简单示例代码。这段代码演示了如何在一个无向图中使用 DFS 进行遍历。
首先，定义图的结构。这里使用邻接列表来表示图，每个顶点都有一个列表，存储与其相邻的顶点。*/using namespace std;class Graph {int V; // 顶点的数量vector<vector<int>> adj; // 邻接列表public:Graph(int V); // 构造函数void addEdge(int v, int w); // 添加边void DFS(int start); // 深度优先搜索
};Graph::Graph(int V) {this->V = V;adj.resize(V);
}void Graph::addEdge(int v, int w) {adj[v].push_back(w); // 将 w 添加到 v 的列表中adj[w].push_back(v); // 由于是无向图，也添加 v 到 w 的列表中
}void Graph::DFS(int start) {vector<bool> visited(V, false); // 创建一个访问标志数组stack<int> stack; // 创建一个栈用于 DFSstack.push(start); // 将起始顶点压入栈while (!stack.empty()) {// 从栈中取出一个顶点int v = stack.top();stack.pop();// 如果该顶点尚未被访问过if (!visited[v]) {cout << v << " "; // 输出顶点visited[v] = true; // 标记该顶点为已访问}// 获取所有未访问的邻接顶点，并将它们压入栈for (auto i = adj[v].rbegin(); i != adj[v].rend(); ++i) {if (!visited[*i]) {stack.push(*i);}}}
}int main() {// 创建一个具有 5 个顶点的图Graph g(5);// 添加边g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(1, 3);g.addEdge(2, 4);g.addEdge(3, 4);cout << "深度优先搜索的遍历顺序是（从顶点 0 开始）: ";g.DFS(0);return 0;
}
控制台输出：
深度优先搜索的遍历顺序是（从顶点 0 开始）: 0 1 2 4 3