Need help with pathfinding... URGENT!!!

[robertstan79]

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++?

[deceptikon]

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[9];

    // Initialize to the stated graph
    tree[0].value = 'A'; tree[0].link.push_back(&tree[1]);
    tree[1].value = 'B'; tree[1].link.push_back(&tree[2]);
    tree[2].value = 'C'; tree[2].link.push_back(&tree[3]); tree[2].link.push_back(&tree[4]);
    tree[3].value = 'D'; tree[3].link.push_back(&tree[5]);
    tree[4].value = 'F'; tree[4].link.push_back(&tree[6]); tree[4].link.push_back(&tree[7]);
    tree[5].value = 'E';
    tree[6].value = 'I';
    tree[7].value = 'G'; tree[7].link.push_back(&tree[8]);
    tree[8].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.