Background

I can't seem to find an existing answer solving this doubt of mine.

In academic books, it seems that DFS is usually presented in both recursive and iterative forms.

The implementations shown usually display the following complexities, where V is the number of vertices, and E the number of edges in the graph. The graph is represented by adjacency lists.

Recursive:

Time: O(V + E)
Space: O(V)

Iterative:

Time: O(V + E)
Space: O(E)

The reason for the discrepancy in the space complexity is because in the iterative version, we're adding all the edges of the current visiting vertex to be "queued" in a stack.

Because of the recursive implementation leading to potential stack-overflows in big graphs, a space-optimised iterative version is desired, which has been mentioned - but not shown - in some academic materials. The key here is to use iterators achieving a final complexity of:

Iterative (Iterators):

Time: O(V + E)
Space: O(V)

Question

Is my implementation correct? It works for my the test below, but I'm not sure if the test is general enough and it is only working for this special case.

Graph Representation

struct Node {
  int data;
  list<Node*> neighbours;
  Node(int val) : data(val) {}
};

Algorithm (Pre-Order DFS)

void preDFSIter(vector<Node*>& adjList) {
    stack<pair<list<Node*>::iterator, list<Node*>::iterator>> nodes;
    unordered_set<Node*> visited;
    for (Node* curStartNode : adjList) {
        if (visited.count(curStartNode)) continue;
        list<Node*> startList = {curStartNode};
        nodes.push({startList.begin(), startList.end()});
        while (!nodes.empty()) {
            auto&[curNodeIt, curNodeItEnd] = nodes.top();
            if (curNodeIt != curNodeItEnd) {
                Node* curNode = *curNodeIt;
                ++curNodeIt;
                if (!visited.count(curNode)) {
                    visited.insert(curNode);
                    cout << to_string(curNode->data) << " ";
                    nodes.push({curNode->neighbours.begin(), curNode->neighbours.end()});
                }
            } else {
                nodes.pop();
            }
        }
    }
    cout << endl;
}

Algorithm (Post-Order DFS)

void postDFSIterVar(vector<Node*>& adjList) {
    unordered_set<Node*> visited;
    stack<tuple<Node*, list<Node*>::iterator, list<Node*>::iterator>> nodes;
    for (Node* curStartNode : adjList) {
        if (visited.count(curStartNode)) continue;
        list<Node*> startList = {curStartNode};
        nodes.push({nullptr, startList.begin(), startList.end()});
        while (!nodes.empty()) {
            auto&[curParent, curNodeIt, curNodeItEnd] = nodes.top();
            if (curNodeIt != curNodeItEnd) {
                Node* curNode = *curNodeIt;
                ++curNodeIt;
                if (!visited.count(curNode)) {
                    visited.insert(curNode);
                    nodes.push({curNode, curNode->neighbours.begin(), curNode->neighbours.end()});
                }
            } else {
                if (curParent) cout << to_string(curParent->data) << " ";
                nodes.pop();
            }
        }
    }
    cout << endl;
}

Main

int main() {
    Node* node0 = new Node(0);
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);
    Node* node6 = new Node(6);
    Node* node7 = new Node(7);
    Node* node8 = new Node(8);
    node0->neighbours = {node1, node2};
    node1->neighbours = {node3, node5};
    node2->neighbours = {node5};
    node3->neighbours = {node3, node6};
    node4->neighbours = {node1, node3, node8};
    node5->neighbours = {node0, node4, node7};
    node6->neighbours = {node4};
    node7->neighbours = {node4, node7};
    node8->neighbours = {node6, node7};
    vector <Node*> adjList = {node0, node1, node2, node3, node4, node5, node6, node7, node8};
    
    preDFSIter(adjList);
    postDFSIter(adjList);
    return 0;
}

```