wrote a recursive depth-first search implementation that works great:

void DFSRecursive(int vertex, const std::vector<std::vector<int>>& graph, std::vector<bool>& visitedVertices) { visitedVertices.at(vertex) = true; for (std::uint8_t i = 0; i < graph.size(); i++) if ((graph.at(vertex).at(i) != 0) && (!visitedVertices.at(i))) DFSRecursive(i, graph, visitedVertices); }

After that, I decided to write a non-recursive implementation, and faced the problem of looping in different parts ... And besides, the algorithm was very slow due to the constant search in the vector. Can someone tell me a more elegant solution and what was the problem? Here is the code itself:

 void DFSNonRecursive(int startVertex, const std::vector<std::vector<int>>& graph) { std::vector<int> visitedVertices; visitedVertices.push_back(startVertex); while (!visitedVertices.empty()) { const int vertex = visitedVertices.back(); bool hasAdjacentVertices = false; for (std::uint8_t i = 0; i < graph.size(); i++) { auto iterator = std::find(visitedVertices.begin(), visitedVertices.end(), i); if ((graph.at(vertex).at(i) != 0) && (iterator == visitedVertices.end())) { visitedVertices.push_back(i); hasAdjacentVertices = true; } } if (!hasAdjacentVertices) visitedVertices.pop_back(); } }
  • one
    And why not do the usual stack? ... what are these torments with the vector? - Harry
  • one
    ru.stackoverflow.com/questions/586601/… - Drawn Raccoon 1:29 pm
  • And how with the help of the stack to track the re-entry into one and the same top? - QuickDzen
  • As elsewhere - using the flag, for example. Kormen has this color flag, for example - white, gray, black. - Harry
  • @Harry, could you give a detailed example of the flags and how to use them? - QuickDzen

0