How to indicate preorder of a spanning tree using the algorithm BFS

Question

I'm doing an implementation of the BFS algorithm in c++ to find a spanning tree, the output for a spanning tree should be shown in preorder, but I have a doubt in the implementation, how I can build a tree if not exactly know how many children have each node?. Considering a tree structure recursive The data structure of the tree can be written as:

typedef struct node 
{
        int val;
        struct node *left, *right;
}*tree; //tree has been typedefed as a node pointer.

But do not think it works this implementation as mentioned before.

This is my function to return the tree in preorder:

void preorder(tree t) 
{
        if(t == NULL)
                return;
        printf("%d ", t->val);
        preorder(t->left);
        preorder(t->right);
}

I also wonder if there is any way to do the preorder of the nodes without using a tree structure.

Answer 1

I have seen two concrete questions in the posting:

1. Is it possible to have a data structure using more than two children in a tree? Of course this is possible. Interestingly, it is even possible with the node structure you posted! Just consider the left pointer to be a pointer to the first child and the right pointer to point to the next sibling. Since breadth first search of a graph implicitly builds up a spanning tree, you can then walk this tree in preorder if you actually represent it somehow.
2. Can you do a preorder walk without using a tree structure? Yes, this is possible, too. Essentially, DFS and BFS are conceptually no different for this: you just have a data structure maintaining the nodes to be visited next. For DFS this is a stack, for BFS this is a queue. You get a preorder walk of the tree (i.e. you visit all children of a node after the parent) if you emit the node number when you insert it into the data structure maintaining the nodes to be visited.

To expand a bit on the second point: a preorder walk of a tree just means that each node is processed prior to it child nodes. When you do a graph search you want to traverse through a connected component of a graph, visiting each node just once, you effectively create an implicit tree. That is, your start node become the root node of the tree. Whenever you visit a node you search for adjacent nodes which haven't been visited, i.e. which isn't marked. If there is such a node, the incident edge becomes a tree node and you mark the node. Since there is always only just one node being actively held you need to remember the nodes which aren't processed, yet, in some data structure, e.g. a stack or a queue (instead of using a stack explicitly you could do recursion which creates the stack implicitly). Now, if you emit the node number the first time you see a node you clearly process it prior to its children, i.e. you end up writing the node number the order of a preorder walk.

If you don't understand this, please whip out a sheet of paper and draw a graph and a queue:

• the nodes with hollow circles and their node number next to them
• the edges with thin lines
• the queue is just rectangles which doesn't contain anything at the start

Now choose a node to become the start node of your search which is the same as the root node of your tree. Write its number into the first empty position in the queue and mark i.e. fill the node. Now proceed with the search:

• look at the node indicated by front of the queue and find an adjacent node which isn't filled:
  • append the node at the back of the queue (i.e. right behind the last node in the rectangle)
  • mark (i.e. fill) the node
  • make the line connecting the two nodes thicker: it is a tree edge now
• if there are no further unmarked adjacent nodes tick the front node in the queue off (i.e. remove it from the queue) and move on to the next node until there are no further nodes

Now the queue rectangle contains a preorder walk of the spanning tree implied by a breadth first search of the graph. The spanning tree is visible using the thicker lines. The algorithm would also work if you treated the rectangle for the queue as a stack but it would be a bit messier because you end up with ticked off nodes between nodes still to be processed: instead of looking at the first unticked node you would look at the last unticked node.

When working with graph algorithms I found it quite helpful to visualize the algorithm. Although it would be nice to have the computer maintain the drawing, the low-tech alternative of drawing things on paper and possibly indicating active nodes by a number of labeled pencils works as well if not better.

Just a comment on the code: whenever you are reading any input, make sure that you successfully read the data. BTW, your code is clearly only C and not C++ code: variable length arrays are not available in C++. In C++ you would use std::vector<int> followOrder(vertexNumber) instead of int followOrder[vertexNumber]. Interestingly, the code isn't C either because it uses e.g. std::queue<int>.