25 #ifndef DEPTH_FIRST_SEARCH_INCLUDED 26 #define DEPTH_FIRST_SEARCH_INCLUDED 58 template <

typename TVertex,

typename TVisit_start,

typename TVisit_end,

59 typename TGet_neighbors,

typename TVertex_less = std::less<TVertex>>

61 TVisit_end visitor_end, TGet_neighbors get_neighbors,

62 std::set<TVertex> &visited_set = std::set<TVertex>{}) {

65 constexpr

int START_VISITING = 0;

67 constexpr

int CURRENT_VERTEX = 1;

70 std::stack<std::tuple<bool, TVertex>> stack;

73 if (!visited_set.insert(start_vertex).second) {

76 stack.emplace(

true, start_vertex);

78 while (!stack.empty()) {

79 std::tuple<bool, TVertex> &elem = stack.top();

80 if (std::get<START_VISITING>(elem)) {

81 visitor_start(std::get<CURRENT_VERTEX>(elem));

83 std::get<START_VISITING>(elem) =

false;

84 for (TVertex neighbor : get_neighbors(std::get<CURRENT_VERTEX>(elem))) {

86 if (visited_set.insert(neighbor).second) {

87 stack.emplace(

true, neighbor);

91 visitor_end(std::get<CURRENT_VERTEX>(elem));

void depth_first_search(TVertex start_vertex, TVisit_start visitor_start, TVisit_end visitor_end, TGet_neighbors get_neighbors, std::set< TVertex > &visited_set=std::set< TVertex >{})

Performs a Depth First Search algorithm on a graph defined by a set of vertexes being an subset of un...

**Definition:** depth_first_search.h:60