+C++ example
In C++, default thread stack limits (typically 1–8 MiB) can still overflow on deep graphs with hundreds of thousands of vertices. Storing Frame{vertex, next} in a std::vector<Frame> keeps the active chain on the heap; re-fetching stack.back() on each iteration avoids dangling references across push_back reallocations.
#include <cstddef>
#include <iostream>
#include <vector>
struct Frame {
int vertex;
std::size_t next;
};
std::vector<int> depthFirst(const std::vector<std::vector<int>>& graph, int start) {
std::vector<bool> seen(graph.size(), false);
std::vector<int> order{start};
// Store the next neighbor index in each frame to resume where recursion would.
std::vector<Frame> stack{{start, 0}};
seen[start] = true;
while (!stack.empty()) {
Frame& frame = stack.back();
const auto& neighbors = graph[frame.vertex];
if (frame.next == neighbors.size()) {
stack.pop_back();
continue;
}
int to = neighbors[frame.next++];
if (seen[to]) continue;
seen[to] = true;
order.push_back(to);
stack.push_back({to, 0});
}
return order;
}
int main() {
const char names[] = {'A', 'B', 'C', 'D', 'E'};
const std::vector<std::vector<int>> graph{{1, 2}, {3}, {3, 4}, {}, {}};
const auto order = depthFirst(graph, 0);
for (std::size_t i = 0; i < order.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << names[order[i]];
}
std::cout << '\n';
return 0;
}
Output:
A,B,D,C,E