I've got what looks like a properly functioning DFS implimentation. The only problem is, I am having trouble coming up with a way to display the post-order traversal of nodes correctly. My assignment is to display the results of a DFS in postorder, but it looks like something is running more times than expected and I'm getting unexpected results.
The DFS function is here:
1 2 3 4 5 6 7 8 9 10 11 12 13
int dfs(int u, Graph G){
G.Visited[u] = 1;
std::vector<int> adjacent_nodes (successors(G, u)); //nodes adjacent to current vertex
std::vector<int>::iterator it = adjacent_nodes.end(); //iterator to move to next unvisited node
do{
it--;
if (!G.Visited[*it])
std::cout << dfs( *it, G ) << " ";
}while (it != adjacent_nodes.begin());
return u;
};
The code that calls the DFS is here:
1 2 3
int target;
s >> target;
std::cout << dfs(target, G) << "\n";
I'm inputting an adjacency matrix like this:
0 1 1
1 0 1
1 1 0
and searching with a target of 2
and the output looks like this:
0 1 1 0 2
The "1 0 2" portion of my output is what I need. I'm not sure why the DFS function executes more times than expected... advice?
If I input a 2-dimensional array, it displays correctly. Anything larger than that and only the last (dimension) numbers in the output are needed. The preceding numbers shouldn't be there.