无权有向图的深度优先搜索迭代器 operator++ C++

要实现无权有向图的深度优先搜索迭代器 operator++，可以使用栈数据结构来实现深度优先搜索算法。以下是一个C++的代码示例：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Graph {
private:
    int numVertices;
    vector<vector<int>> adjList;

public:
    Graph(int numVertices) : numVertices(numVertices), adjList(numVertices) {}

    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
    }

    class DFSIterator {
    private:
        vector<bool> visited;
        stack<int> dfsStack;
        int currentVertex;
        const Graph& graph;

    public:
        DFSIterator(const Graph& g) : graph(g) {
            visited.assign(graph.numVertices, false);
            dfsStack.push(0);
            currentVertex = -1;
            ++(*this);  // Start the iterator by visiting the first vertex
        }

        int operator*() const {
            return currentVertex;
        }

        DFSIterator& operator++() {
            if (dfsStack.empty()) {
                currentVertex = -1;  // Mark the end of iteration
                return *this;
            }

            currentVertex = dfsStack.top();
            dfsStack.pop();
            visited[currentVertex] = true;

            for (int neighbor : graph.adjList[currentVertex]) {
                if (!visited[neighbor]) {
                    dfsStack.push(neighbor);
                }
            }

            // Find the next unvisited vertex
            while (!dfsStack.empty() && visited[dfsStack.top()]) {
                dfsStack.pop();
            }

            return *this;
        }

        bool operator!=(const DFSIterator& other) const {
            return currentVertex != other.currentVertex;
        }
    };

    DFSIterator begin() const {
        return DFSIterator(*this);
    }

    DFSIterator end() const {
        return DFSIterator(*this);
    }
};

int main() {
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    g.addEdge(3, 5);

    for (int vertex : g) {
        cout << vertex << " ";
    }
    cout << endl;

    return 0;
}

在上述代码中，我们定义了一个Graph类表示无权有向图。内部嵌套了一个DFSIterator类作为深度优先搜索迭代器。DFSIterator类包含了一个visited向量用于标记已访问的顶点，一个dfsStack栈用于保存需要访问的顶点，一个currentVertex变量表示当前迭代器指向的顶点，以及一个对Graph类的引用graph用于获取图的邻接列表。

在DFSIterator类中，构造函数初始化visited向量和dfsStack栈，并将起始顶点0推入dfsStack中。迭代器的operator++方法实现了深度优先搜索算法。它首先将dfsStack栈顶弹出并将其赋值给currentVertex，然后将currentVertex标记为已访问。接下来，将currentVertex的未访问邻居顶点推入dfsStack中。最后，使用while循环查找dfsStack中下一个未访问的顶点，直到找到或者dfsStack为空。迭代器的operator*方法返回当前顶点的值。迭代器的operator!=方法用于判断迭代器是否到达结束位置。

在main函数中，我们创建了一个有6个顶点的图，并添加了一些边。然后，我们使用范围for循环来迭代图中的顶点，并输出它们的值。

输出结果为：0 4 1 3 5 2，表示深度优先搜索的顶点访问顺序。