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:

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)

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

    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.

This article has been dead for over six months. Start a new discussion instead.