+C++20
The C++20 version stores the vertex and next-neighbor position in a Frame, preserving where recursive DFS would resume. The start and every neighbor must be valid indices into graph. On the same graph, it discovers A,B,D,C,E.
#include <cstddef>
#include <iostream>
#include <vector>
using Graph = std::vector<std::vector<std::size_t>>;
struct Frame { std::size_t vertex; std::size_t next; };
std::vector<std::size_t> depthFirst(const Graph& graph, std::size_t start) {
std::vector<bool> seen(graph.size(), false);
std::vector<std::size_t> order{start};
std::vector<Frame> stack{{start, 0}};
seen[start] = true;
while (!stack.empty()) {
auto& frame = stack.back();
const auto& neighbors = graph[frame.vertex];
if (frame.next == neighbors.size()) {
stack.pop_back();
continue;
}
// Advance the saved position before exploring a child so the parent resumes correctly.
const auto 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 std::vector<char> names{'A', 'B', 'C', 'D', 'E'};
const Graph 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;
}
A,B,D,C,E
TypeScript