c++实现深度优先搜索
c++实现深度优先搜索
·
以下是一个用C++实现深度优先搜索(DFS)的简单示例代码:
#include <iostream>
#include <list>
#include <stack>
#include <vector>
using namespace std;
class Graph {
int V;
list<int> *adj; // 邻接表
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int s);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::DFS(int s) {
vector<bool> visited(V, false);
stack<int> stack;
stack.push(s);
while (!stack.empty()) {
s = stack.top();
stack.pop();
if (!visited[s]) {
cout << s << " ";
visited[s] = true;
}
for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
if (!visited[*i]) {
stack.push(*i);
}
}
}
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Depth First Traversal (starting from vertex 2): ";
g.DFS(2);
return 0;
}
在这个示例中,我们首先定义了一个 Graph
类,其中包含了图的顶点数 V
和邻接表 adj
。我们可以使用 addEdge
方法向图中添加边。在 DFS
方法中,我们使用一个栈来实现深度优先搜索。我们从给定的起始顶点开始,将其压入栈中,并在每次迭代中访问该顶点以及其未访问过的相邻顶点,并将它们压入栈中。
在 main
函数中,我们创建了一个图并添加了一些边,然后从顶点2开始进行深度优先搜索,并输出遍历结果。
这是一个简单的深度优先搜索的实现示例,实际应用中可能需要根据具体需求进行适当的调整和扩展。
更多推荐
已为社区贡献1条内容
所有评论(0)