Postorder traversal in depth-first search

Apr 28, 2013 at 3:09am
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?
Apr 28, 2013 at 3:14am
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.
Apr 28, 2013 at 3:26am
If it's relevent, the successors() function is here:
1
2
3
4
5
6
7
8
std::vector<int> successors( Graph G, int NodeNumber){
	std::vector<int> adjacent_nodes;
	for (int i = 0; i < G.NodeCount; i++){
		if (G.A[NodeNumber][i] == 1)
			adjacent_nodes.push_back(i);
	}
	return adjacent_nodes;
};
Topic archived. No new replies allowed.