Hi, I am writing a program that uses post-order breadth first tree-traversal to give me a path navigating from one point in my house to another. Here is a map of my house: http://postimage.org/image/3vq80wdkx/. Here is the tree that I need to traverse and list all the possibilites of: http://postimage.org/image/nlbv9dp03/. For example, the possibilites are:
AB
ABC
ABCD
ABCDE
ABCF
ABCFI
ABCFIG
ABCFIH

How do I implement this in C++?

How are you storing the graph? That kind of matters in the implementation. ;) Another critical factor would be whether there's a cycle in the graph or not. It's simpler if you don't have to consider revisiting a node.

In fact, if there are no cycles then you can probably store the graph as a tree and call it good with a simple preorder traversal:

``````#include <iostream>
#include <vector>

using namespace std;

struct node
{
char value;
vector<node*> link;
};

void PreOrder(node* root)
{
cout << root->value << ' ';

for (vector<node*>::size_type i = 0; i < root->link.size(); ++i)
{
PreOrder(root->link[i]);
}
}

int main(void)
{
node tree;

// Initialize to the stated graph
tree.value = 'A'; tree.link.push_back(&tree);
tree.value = 'B'; tree.link.push_back(&tree);
tree.value = 'C'; tree.link.push_back(&tree); tree.link.push_back(&tree);
tree.value = 'D'; tree.link.push_back(&tree);
tree.value = 'F'; tree.link.push_back(&tree); tree.link.push_back(&tree);
tree.value = 'E';
tree.value = 'I';
tree.value = 'G'; tree.link.push_back(&tree);
tree.value = 'H';

// Do a straight inorder traversal to display
PreOrder(tree);

return 0;
}
``````

The only trick from there would be saving the current path at each node, which constitutes most of the effort of this solution after making the connection between your graph and a multi-way tree where a preorder traversal accomplishes the goal of pathfinding.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.