深度优先搜索算法c++
时间: 2023-07-27 10:08:25 浏览: 69
深度优先搜索算法(Depth-First Search,简称DFS)是一种用于遍历或搜索树或图的算法。以下是一个基于C++的深度优先搜索算法示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 定义图的邻接表表示
class Graph {
int numVertices; // 图中顶点的数量
vector<vector<int>> adjLists; // 邻接表
public:
Graph(int vertices) {
numVertices = vertices;
adjLists.resize(numVertices);
}
// 添加边
void addEdge(int src, int dest) {
adjLists[src].push_back(dest);
adjLists[dest].push_back(src);
}
// 深度优先搜索递归函数
void DFSUtil(int vertex, vector<bool>& visited) {
visited[vertex] = true;
cout << vertex << " ";
// 对邻接顶点进行递归调用
for (int adjVertex : adjLists[vertex]) {
if (!visited[adjVertex]) {
DFSUtil(adjVertex, visited);
}
}
}
// 深度优先搜索
void DFS(int startVertex) {
vector<bool> visited(numVertices, false); // 记录顶点是否访问过
DFSUtil(startVertex, visited);
}
};
int main() {
Graph g(6); // 创建一个有6个顶点的图
// 添加边
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(3, 5);
cout << "深度优先搜索结果: ";
g.DFS(0);
return 0;
}
```
以上代码实现了一个简单的无向图,并使用深度优先搜索算法遍历图中的顶点。输出结果为从起始顶点开始的深度优先搜索顺序。你可以根据需要修改图的大小和边的连接关系。