以下是一个用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开始进行深度优先搜索,并输出遍历结果。

这是一个简单的深度优先搜索的实现示例,实际应用中可能需要根据具体需求进行适当的调整和扩展。

Logo

腾讯云面向开发者汇聚海量精品云计算使用和开发经验,营造开放的云计算技术生态圈。

更多推荐