+C++ 예제
C++에서도 운영체제 스레드 기본 스택 크기(보통 1~8 MiB)는 깊이가 수십만인 경로 그래프에서 재귀 호출 시 스택 오버플로를 일으킬 수 있다. std::vector<Frame>에 정점 번호와 이웃 인덱스 next를 함께 보관하되, stack.push_back이 재할당을 일으킬 수 있으므로 매 반복마다 stack.back() 참조를 새로 읽는다.
#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};
// 각 정점에서 다음에 읽을 이웃 인덱스(next)를 저장해 재귀 복귀 지점을 모사한다.
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;
}
실행 결과:
A,B,D,C,E